Routing in a polygonal terrain with the shortest beacon watchtower (Q1699277)

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.