Routing in a polygonal terrain with the shortest beacon watchtower

DOI10.1016/j.comgeo.2017.05.005zbMath1396.65050OpenAlexW2613478341MaRDI QIDQ1699277

David Rappaport, Bahram Kouhestani, 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

greedy routingbeacon attractionbeacon kernelbeacon watchtowerinverse beacon kernel

Mathematics Subject Classification ID

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

Related Items (3)

Gathering by repulsion ⋮ Gathering by Repulsion. ⋮ An optimal algorithm to compute the inverse beacon attraction region

Cites Work

• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• Ray shooting in polygons using geodesic triangulations
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• Beacon-Based Algorithms for Geometric Routing
• A Lower Bound to Finding Convex Hulls

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