An optimal algorithm to compute the inverse beacon attraction region

I. Kostitsyna, Bahram Kouhestani, Stefan Langerman, David Rappaport

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Uittreksel


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.
TaalEngels
TitelProc. 34th International Symposium on Computational Geometry (SoCG)
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's55:1-55:14
ISBN van elektronische versie978-3-95977-066-8
DOI's
StatusGepubliceerd - 2018
Evenement34th International Symposium on Computational Geometry (SoCG 2018) - Budapest, Hongarije
Duur: 11 jun 201814 jun 2018

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
UitgeverijSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Volume99
ISSN van elektronische versie1868-8969

Congres

Congres34th International Symposium on Computational Geometry (SoCG 2018)
LandHongarije
StadBudapest
Periode11/06/1814/06/18

Vingerafdruk

Trees (mathematics)
Robotics
Trajectories

Citeer dit

Kostitsyna, I., Kouhestani, B., Langerman, S., & Rappaport, D. (2018). An optimal algorithm to compute the inverse beacon attraction region. In Proc. 34th International Symposium on Computational Geometry (SoCG) (blz. 55:1-55:14). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 99). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.SoCG.2018.55
Kostitsyna, I. ; Kouhestani, Bahram ; Langerman, Stefan ; Rappaport, David. / An optimal algorithm to compute the inverse beacon attraction region. Proc. 34th International Symposium on Computational Geometry (SoCG). Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. blz. 55:1-55:14 (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{f9281b1a8d81410886439b4035cbae2c,
title = "An optimal algorithm to compute the inverse beacon attraction region",
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.",
author = "I. Kostitsyna and Bahram Kouhestani and Stefan Langerman and David Rappaport",
year = "2018",
doi = "10.4230/LIPIcs.SoCG.2018.55",
language = "English",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "55:1--55:14",
booktitle = "Proc. 34th International Symposium on Computational Geometry (SoCG)",

}

Kostitsyna, I, Kouhestani, B, Langerman, S & Rappaport, D 2018, An optimal algorithm to compute the inverse beacon attraction region. in Proc. 34th International Symposium on Computational Geometry (SoCG). Leibniz International Proceedings in Informatics (LIPIcs), vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, blz. 55:1-55:14, Budapest, Hongarije, 11/06/18. DOI: 10.4230/LIPIcs.SoCG.2018.55

An optimal algorithm to compute the inverse beacon attraction region. / Kostitsyna, I.; Kouhestani, Bahram; Langerman, Stefan; Rappaport, David.

Proc. 34th International Symposium on Computational Geometry (SoCG). Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. blz. 55:1-55:14 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 99).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

TY - GEN

T1 - An optimal algorithm to compute the inverse beacon attraction region

AU - Kostitsyna,I.

AU - Kouhestani,Bahram

AU - Langerman,Stefan

AU - Rappaport,David

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.SoCG.2018.55

DO - 10.4230/LIPIcs.SoCG.2018.55

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 55:1-55:14

BT - Proc. 34th International Symposium on Computational Geometry (SoCG)

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

ER -

Kostitsyna I, Kouhestani B, Langerman S, Rappaport D. An optimal algorithm to compute the inverse beacon attraction region. In Proc. 34th International Symposium on Computational Geometry (SoCG). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2018. blz. 55:1-55:14. (Leibniz International Proceedings in Informatics (LIPIcs)). Beschikbaar vanaf, DOI: 10.4230/LIPIcs.SoCG.2018.55