On the Discrete and Semi-continuous Versions of the Two-Watchtower Problem in the Plane
摘要
We consider the two-watchtower problem in the plane in which, given a 1.5-dimensional terrain T, we want to compute the minimum common height of two watchtowers that are erected at points of T and together guard the entire T. The problem is encountered in three versions, the discrete, the semi-continuous, and the continuous [1, 3, 5]. In this paper, we focus on the discrete and semi-continuous versions of the problem. We prove important geometric properties of the problem which enable us to describe a simpler and faster decision process for each of these two versions; this leads to a faster \(O(n^2 \log ^2 n)\) -time algorithm for the discrete two-watchtower problem and an algorithm matching the complexity of the algorithm in [1] for the semi-continuous version. Additionally, for the discrete version, we present a simple algorithm that does not use parametric search; it runs in \(O(n^3 \log n)\) time, which improves upon the currently best algorithm for this problem.