An optimal algorithm to compute the inverse beacon attraction region

DOI10.4230/LIPICS.SOCG.2018.55MaRDI QIDQ5115823zbMATH OpenOpenAlexFDO

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

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1803.05946

zbMATH Keywords

optimalityalgorithmbeacon attractioninverse attraction region

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40)

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(nlogn)$ 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(nlogn)$ lower bound for this task in the algebraic computation tree model of computation, even if the polygon is monotone.

Recommendations

• A combinatorial bound for beacon-based routing in orthogonal polygons
• Attraction-convexity and normal visibility
• Routing in a polygonal terrain with the shortest beacon watchtower
• Beacon-based algorithms for geometric routing
• Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons

Cites work

• scientific article; zbMATH DE number 1617248 (Why is no real title available?)
• A Lower Bound to Finding Convex Hulls
• A combinatorial bound for beacon-based routing in orthogonal polygons
• An optimal algorithm to compute the inverse beacon attraction region
• Beacon-based algorithms for geometric routing
• Euclidean shortest paths in the presence of rectilinear barriers
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Routing in a polygonal terrain with the shortest beacon watchtower
• Routing with guaranteed delivery in ad hoc wireless networks
• Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons
• Visibility and intersection problems in plane geometry

Cited in

(8)

• A sub-quadratic time algorithm for computing the beacon kernel of simple polygons
• An optimal algorithm to compute the inverse beacon attraction region
• Optimization of configurations of four beacons in a difference range finding navigation system within the visibility cone
• Gathering by repulsion
• Beacon-based algorithms for geometric routing
• A combinatorial bound for beacon-based routing in orthogonal polygons
• Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
• Negative instance for the edge patrolling beacon problem

This page was built for publication: An optimal algorithm to compute the inverse beacon attraction region

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115823)