Document Open Access Logo

An Optimal Algorithm to Compute the Inverse Beacon Attraction Region

Authors Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman, David Rappaport

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.55.pdf
  • Filesize: 0.73 MB
  • 14 pages

Document Identifiers

Author Details

Irina Kostitsyna
Bahram Kouhestani
Stefan Langerman
David Rappaport

Cite As Get BibTex

Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman, and David Rappaport. An Optimal Algorithm to Compute the Inverse Beacon Attraction Region. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.55

Abstract

The beacon model is a recent paradigm for guiding the trajectory of messages or small robotic agents in complex environments. A beacon is a fixed point with an attraction pull that can move points within a given polygon. Points move greedily towards a beacon: if unobstructed, they move along a straight line to the beacon, and otherwise they slide on the edges of the polygon. The Euclidean distance from a moving point to a beacon is monotonically decreasing. A given beacon attracts a point if the point eventually reaches the beacon.
The problem of attracting all points within a polygon with a set of beacons can be viewed as a variation of the art gallery problem. Unlike most variations, the beacon attraction has the intriguing property of being asymmetric, leading to separate definitions of attraction region and inverse attraction region. The attraction region of a beacon is the set of points that it attracts. It is connected and can be computed in linear time for simple polygons. By contrast, it is known that the inverse attraction region of a point - the set of beacon positions that attract it - could have Omega(n) disjoint connected components.
In this paper, we prove that, in spite of this, the total complexity of the inverse attraction region of a point in a simple polygon is linear, and present a O(n log n) time algorithm to construct it. This improves upon the best previous algorithm which required O(n^3) time and O(n^2) space. Furthermore we prove a matching Omega(n log n) lower bound for this task in the algebraic computation tree model of computation, even if the polygon is monotone.

Subject Classification

Keywords
  • beacon attraction
  • inverse attraction region
  • algorithm
  • optimal

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sang Won Bae, Chan-Su Shin, and Antoine Vigneron. Tight bounds for beacon-based coverage in simple rectilinear polygons. In Proc. 12th Latin American Symposium on Theoretical Informatics, 2016. Google Scholar
  2. Michael Biro. Beacon-based routing and guarding. PhD thesis, Stony Brook University, 2013. Google Scholar
  3. Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. Beacon-based routing and coverage. In Abstr. 21st Fall Workshop on Computational Geometry, 2011. Google Scholar
  4. Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. Combinatorics of beacon-based routing and coverage. In Proc. 25th Canadian Conference on Computational Geometry, 2013. Google Scholar
  5. Michael Biro, Justin Iwerks, Irina Kostitsyna, and Joseph S. B. Mitchell. Beacon-based algorithms for geometric routing. In Proc. 13th Algorithms and Data Structures Symposium, 2013. Google Scholar
  6. Prosenjit Bose, Pat Morin, Ivan Stojmenović, and Jorge Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wirel. Netw., 7(6):609-616, 2001. URL: http://dx.doi.org/10.1023/A:1012319418150.
  7. Gerth S. Brodal and Riko Jacob. Dynamic planar convex hull. In Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Google Scholar
  8. Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geometry. Discrete & Computational Geometry, 4(6):551-581, 1989. Google Scholar
  9. Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1-4):209-233, 1987. Google Scholar
  10. Brad Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, MobiCom '00, pages 243-254, New York, NY, USA, 2000. ACM. URL: http://dx.doi.org/10.1145/345910.345953.
  11. Anne-Marie Kermarrec and Guang Tan. Greedy geographic routing in large-scale sensor networks: A minimum network decomposition approach. IEEE/ACM Transactions on Networking, 20:864-877, 2010. Google Scholar
  12. Irina Kostitsyna, Bahram Kouhestani, Stefan Langerman, and David Rappaport. An optimal algorithm to compute the inverse beacon attraction region. ArXiv e-prints, http://arxiv.org/abs/1803.05946, 2018.
  13. Bahram Kouhestani, David Rappaport, and Kai Salomaa. The length of the beacon attraction trajectory. In Proc. 27th Canadian Conference on Computational Geometry, 2015. Google Scholar
  14. Bahram Kouhestani, David Rappaport, and Kai Salomaa. On the inverse beacon attraction region of a point. In Proc. 27th Canadian Conference on Computational Geometry, 2015. Google Scholar
  15. Bahram Kouhestani, David Rappaport, and Kai Salomaa. Routing in a polygonal terrain with the shortest beacon watchtower. International Journal of Computational Geometry &Applications, 68:34-47, 2018. Google Scholar
  16. Der-Tsai Lee and Franco P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14(3):393-410, 1984. Google Scholar
  17. Thomas Shermer. A combinatorial bound for beacon-based routing in orthogonal polygons. In Proc. 27th Canadian Conference on Computational Geometry, 2015. Google Scholar
  18. Andrew C. Yao. A lower bound to finding convex hulls. Journal of the ACM, 28(4):780-787, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact