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 investigate the problem of assembling general shapes and patterns in amodel in which particles move based on uniform external forces until theyencounter an obstacle. While previous work within this model of assembly hasfocused on designing a specific board configuration for the assembly of aspecific given shape, we propose the problem of designing universalconfigurations that are capable of constructing a large class of shapes andpatterns. In particular, for given integers $h,w$, we show that there exists astrongly universal configuration (no excess particles) with $\mathcal{O}(hw)$$1 \times 1$ slidable particles that can be reconfigured to build any $h \timesw$ patterned rectangle. We then expand this result to show that there exists aweakly universal configuration that can build any $h \times w$-bounded sizeconnected shape. Following these results, we go on to show the existence of astrongly universal configuration which can assemble any shape within apreviously studied ``drop'' class, while using quadratically less space thanprevious results.  Finally, we include a study of the complexity of motion planning in thismodel. We consider the problems of deciding if a board location can be occupiedby any particle (occupancy problem), deciding if a specific particle may berelocated to another position (relocation problem), and deciding if a givenconfiguration of particles may be transformed into a second given configuration(reconfiguration problem). We show all of these problems to be PSPACE-completewith the allowance of a single $2\times 2$ polyomino in addition to $1\times 1$tiles. We further show that relocation and occupancy remain PSPACE-completeeven when the board geometry is a simple rectangle if domino polyominoes areincluded.

Full Tilt: Universal Constructors for General Shapes with Uniform External Forces