Vi presenterar algoritmiska resultat för parallell montering av många mikroskalobjekt i två och tre dimensioner från små partiklar, vilket har föreslagits i samband med programmerbar materia och självmontering för att bygga högavkastade mikrofabriker. Den underliggande modellen har partiklar som rör sig under påverkan av enhetliga yttre krafter tills de träffar ett hinder. Partiklar binder ihop när de tvingas ihop med en annan lämplig partikel. På grund av de fysiska och geometriska begränsningarna kan inte alla former byggas på detta sätt; detta ger upphov till Tilt Assembly Problem (TAP) att avgöra konstruktionsförmåga. För enkelt anslutna polyominoes P i 2D som består av N-enheter-kvartor ("tilar"), visar vi att TAP kan beslutas i O (N log N ) tid. För optimeringsvarianten MaxTAP (där syftet är att konstruera en subform av maximal storlek) visar vi polyAPX-hårdhet: om inte P = NP, MaxTAP inte kan approximeras inom en faktor av (N 1 3 ); för trädformade strukturer, ger vi en (N 1 2 ) - approximation algoritm. För effektiviteten i själva monteringsprocessen, visar vi att alla konstruktionsbara form tillåter rörledning montering, som producerar kopior av P i O(1) avkortad tid, dvs N kopior av P i O(N ) tidssteg. Dessa överväganden kan utvidgas till tredimensionella objekt: För klassen av polykuber P visar vi att det är NP-hårdt att avgöra om det är möjligt att konstruera en väg mellan två punkter av P; det är också NP-hård att bestämma konstruktionsförmågan hos en polycube P. Dessutom är det expAPX-hård att maximera en sekventiellt konstruktörsbar väg från en given startpunkt.
Becker m.fl. REF visar att det är möjligt att bestämma i polynom tid om en hålfri polyomino kan konstrueras.
Tilt Assembly: Algorithms for Micro-factories That Build Objects with Uniform External Forces
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}