Tilt assembly: algorithms for micro-factories that build objects with uniform external forces

DOI10.1007/s00453-018-0483-9zbMath1433.68167OpenAlexW2963328945WikidataQ129426791 ScholiaQ129426791MaRDI QIDQ1986953

Phillip Keldenich, Aaron Becker, Christian Scheffer, Sándor P. Fekete, Arne Schmidt, Christian Rieck, Dominik Krupke

Publication date: 9 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8221/

zbMATH Keywords

approximationhardnessprogrammable mattertile assemblytiltmicro-factories

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Coordinating Swarms of Objects at Extreme Dimensions ⋮ Fast reconfiguration of robot swarms with uniform control signals ⋮ Particle-based assembly using precise global control

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New geometric algorithms for fully connected staged self-assembly
• Universal coating for programmable matter
• Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
• On the complexity of approximating the independent set problem
• Reconfiguring massive particle swarms with limited, global control
• Leader Election and Shape Formation with Self-organizing Programmable Matter
• The program-size complexity of self-assembled squares (extended abstract)
• Running time and program size for self-assembled squares
• Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
• Parallelism and Time in Hierarchical Self-Assembly