LIPIcs.SWAT.2018.13.pdf
- Filesize: 2.11 MB
- 12 pages
Document
Gathering by Repulsion
Authors
-
Part of:
Volume:
16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-04
Cite As Get BibTex
Prosenjit Bose and Thomas C. Shermer. Gathering by Repulsion. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SWAT.2018.13
Abstract
We consider a repulsion actuator located in an n-sided convex environment full of point particles. When the actuator is activated, all the particles move away from the actuator. We study the problem of gathering all the particles to a point. We give an O(n^2) time algorithm to compute all the actuator locations that gather the particles to one point with one activation, and an O(n) time algorithm to find a single such actuator location if one exists. We then provide an O(n) time algorithm to place the optimal number of actuators whose sequential activation results in the gathering of the particles when such a placement exists.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph theory
- Theory of computation → Design and analysis of algorithms
- Theory of computation → Computational geometry
Keywords
- polygon
- kernel
- beacon attraction
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Sang Won Bae, Chan-Su Shin, and Antoine Vigneron. Improved bounds for beacon-based coverage and routing in simple rectilinear polygons. arXiv preprint arXiv:1505.05106, 2015.
-
Michael Biro. Beacon-based routing and guarding. PhD thesis, State University of New York at Stony Brook, 2013.
-
Michael Biro, Justin Iwerks, Irina Kostitsyna, and Joseph SB Mitchell. Beacon-based algorithms for geometric routing. In WADS, pages 158-169. 2013.
-
Herbert Edelsbrunner and Leonidas J. Guibas. Topologically sweeping an arrangement. J. Comput. Syst. Sci., 38(1):165-194, 1989.
-
Herbert Edelsbrunner and Leonidas J. Guibas. Corrigendum: Topologically sweeping an arrangement. J. Comput. Syst. Sci., 42(2):249-251, 1991.
-
Leonidas J. Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and computation of voronoi diagrams. ACM Trans. Graph., 4(2):74-123, 1985.
-
Christian Icking, Rolf Klein, and Elmar Langetepe. Self-approaching curves. Math. Proc. Camb. Phil. Soc., 123(3):441-453, 1999.
-
Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman, and David Rappaport. An optimal algorithm to compute the inverse beacon attraction region. In SoCG, 2018.
-
Bahram Kouhestani, David Rappaport, and Kai Salomaa. On the inverse beacon attraction region of a point. In CCCG, 2015.
-
Bahram Kouhestani, David Rappaport, and Kai Salomaa. The length of the beacon attraction trajectory. In CCCG, pages 69-74, 2016.
-
Bahram Kouhestani, David Rappaport, and Kai Salomaa. Routing in a polygonal terrain with the shortest beacon watchtower. Comput. Geom., 68:34-47, 2018.
-
Nimrod Megiddo. Linear-time algorithms for linear programming in ℝ³ and related problems. SIAM J. Comput., 12(4):759-776, 1983.
-
Michael Shamos. Computational Geometry. PhD thesis, Yale Univeristy, 1978.
-
Thomas C Shermer. A combinatorial bound for beacon-based routing in orthogonal polygons. arXiv preprint arXiv:1507.03509, 2015.
-
Emo Welzl. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, pages 359-370, 1991.