Routing in a polygonal terrain with the shortest beacon watchtower

DOI10.1016/J.COMGEO.2017.05.005MaRDI QIDQ1699277zbMATH OpenOpenAlexFDO

Authors Bahram Kouhestani, David Rappaport, Kai Salomaa

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2017.05.005

zbMATH Keywords

beacon attractionbeacon kernelbeacon watchtowergreedy routinginverse beacon kernel

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

The problem of computing the shortest watchtower to guard a 2D terrain is approached in this paper, improving the existing techniques by using the properties of beacons. An \(O(n \log(n))\) time algorithm that computes the shortest beacon watchtower is presented. The authors define the shortest beacon watchtower as a beacon on the upper endpoint of a vertical line segment erected on the terrain which can send and receive messages from any other point on the terrain. The authors start the construction of the new algorithm by elaborating algorithms to compute the beacon kernel and the inverse beacon kernel in a monotone polygon. The shortest beacon watchtower is computed by intersecting the kernel and inverse beacon kernel of the terrain polygon. The complexity of calculus of the new algorithm is discussed.

Recommendations

• The shortest watchtower and related problems for polyhedral terrains
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES
• Finding the shortest watchman route in a simple polygon
• Fast computation of shortest watchman routes in simple polygons

Cites work

• A Lower Bound to Finding Convex Hulls
• Beacon-based algorithms for geometric routing
• Computational geometry. Algorithms and applications.
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• Finding the upper envelope of n line segments in O(n log n) time
• Ray shooting in polygons using geodesic triangulations

Cited in

(8)

• Watchman routes in the presence of a pair of convex polygons
• Gathering by repulsion
• Tight bounds for beacon-based coverage in simple rectilinear polygons
• Beacon-based algorithms for geometric routing
• A combinatorial bound for beacon-based routing in orthogonal polygons
• An optimal algorithm to compute the inverse beacon attraction region
• Gathering by repulsion
• Chasing puppies: mobile beacon routing on closed curves

This page was built for publication: Routing in a polygonal terrain with the shortest beacon watchtower

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