English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present algorithmic results for the parallel assembly of many micro-scaleobjects in two and three dimensions from tiny particles, which has beenproposed in the context of programmable matter and self-assembly for buildinghigh-yield micro-factories. The underlying model has particles moving under theinfluence of uniform external forces until they hit an obstacle; particles canbond when being forced together with another appropriate particle. Due to thephysical and geometric constraints, not all shapes can be built in this manner;this gives rise to the Tilt Assembly Problem (TAP) of decidingconstructibility. For simply-connected polyominoes $P$ in 2D consisting of $N$unit-squares ("tiles"), we prove that TAP can be decided in $O(N\log N)$ time.For the optimization variant MaxTAP (in which the objective is to construct asubshape of maximum possible size), we show polyAPX-hardness: unless P=NP,MaxTAP cannot be approximated within a factor of $\Omega(N^{\frac{1}{3}})$; fortree-shaped structures, we give an $O(N^{\frac{1}{2}})$-approximationalgorithm. For the efficiency of the assembly process itself, we show that anyconstructible shape allows pipelined assembly, which produces copies of $P$ in$O(1)$ amortized time, i.e., $N$ copies of $P$ in $O(N)$ time steps. Theseconsiderations can be extended to three-dimensional objects: For the class ofpolycubes $P$ we prove that it is NP-hard to decide whether it is possible toconstruct a path between two points of $P$; it is also NP-hard to decideconstructibility of a polycube $P$. Moreover, it is expAPX-hard to maximize apath from a given start point.

Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces