Abstract
In micro- and nano-scale systems, particles can be moved by using an external force such as gravity or a magnetic field. In the presence of adhesive particles that can attach to each other, the challenge is to decide whether a shape is constructible. Previous work provides a class of shapes for which constructibility can be decided efficiently, when particles move maximally into the same direction on actuation.
In this paper, we consider a stronger model. On actuation, each particle moves one unit step into the given direction. We prove that deciding constructibility is NP-hard for three-dimensional shapes, and that a maximum constructible shape can be approximated. The same approximation algorithm applies for 2D. We further present linear-time algorithms to decide whether a tree-shape in 2D or 3D is constructible. If scaling is allowed, we show that the c-scaled copy of every non-degenerate polyomino is constructible, for every \(c \ge 2\).
Due to space constraints, several technical details and proofs are omitted from this extended abstract. A full version of the paper can be found at [12].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, P.K., Aronov, B., Geft, T., Halperin, D.: On two-handed planar assembly partitioning. In: Proceedings of the Symposium on Discrete Algorithms (2021)
Balanza-Martinez, J., et al.: Hierarchical shape construction and complexity for slidable polyominoes under uniform external forces. In: Proceedings of the Symposium on Discrete Algorithms (2020)
Balanza-Martinez, J., et al.: Full tilt: universal constructors for general shapes with uniform external forces. In: Proceedings of the Symposium on Discrete Algorithms (2019)
Becker, A., Demaine, E.D., Fekete, S.P., Habibi, G., McLurkin, J.: Reconfiguring massive particle swarms with limited, global control. In: Flocchini, P., Gao, J., Kranakis, E., Meyer auf der Heide, F. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 51–66. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-45346-5_5
Becker, A.T., et al.: Targeted drug delivery: algorithmic methods for collecting a swarm of particles with uniform, external forces. In: International Conference on Robotics and Automation (2020)
Becker, A.T., et al.: Tilt assembly: algorithms for micro-factories that build objects with uniform external forces. Algorithmica (2018)
de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22, 187–205 (2012)
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Building patterned shapes in robot swarms with uniform control signals. In: Proceedings of the Canadian Conference on Computational Geometry (2020)
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Hardness of reconfiguring robot swarms with uniform external control in limited directions. J. Inf. Process. 28, 782–790 (2020)
Caballero, D., Cantu, A.A., Gomez, T., Luchsinger, A., Schweller, R., Wylie, T.: Relocating units in robot swarms with uniform control signals is PSPACE-complete. In: Proceedings of the Canadian Conference on Computational Geometry (2020)
Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55, 78–88 (2012)
Keller, J., Rieck, C., Scheffer, C., Schmidt, A.: Particle-based assembly using precise global control. arXiv:2105.05784 (2021)
Mahadev, A.V., Krupke, D., Reinhardt, J.M., Fekete, S.P., Becker, A.T.: Collecting a swarm in a grid environment using shared, global inputs. In: International Conference on Automation Science and Engineering (2016)
Manzoor, S., Sheckman, S., Lonsford, J., Kim, H., Kim, M.J., Becker, A.T.: Parallel self-assembly of polyominoes under uniform control inputs. Robot. Autom. Lett. 2, 2040–2047 (2017)
Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Natural Comput. 13, 195–224 (2014)
Rothemund, P.W.: Design of DNA origami. In: International Conference on Computer-Aided Design (2005)
Rothemund, P.W., Winfree, E.: The Program-size complexity of self-assembled squares. In: Proceedings of the Symposium on Theory of Computing (2000)
Schmidt, A., Manzoor, S., Huang, L., Becker, A.T., Fekete, S.P.: Efficient parallel self-assembly under uniform control inputs. Robot. Autom. Lett. 3, 3521–3528 (2018)
Wang, H.: Proving theorems by pattern recognition-II. Bell Syst. Tech. J. 40, 1–41 (1961)
Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology (1998)
Woods, D.: Intrinsic Universality and the Computational Power of Self-Assembly. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (2015)
Acknowledgements
We thank Linda Kleist for valuable discussions and suggestions that improved the presentation of this paper, Matthias Konitzny for the awesome 3D images, and the anonymous reviewers for providing helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Keller, J., Rieck, C., Scheffer, C., Schmidt, A. (2021). Particle-Based Assembly Using Precise Global Control. In: Lubiw, A., Salavatipour, M., He, M. (eds) Algorithms and Data Structures. WADS 2021. Lecture Notes in Computer Science(), vol 12808. Springer, Cham. https://doi.org/10.1007/978-3-030-83508-8_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-83508-8_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-83507-1
Online ISBN: 978-3-030-83508-8
eBook Packages: Computer ScienceComputer Science (R0)