Optimistic Imprecise Shortest Watchtower in 1.5D and 2.5D
Bradley McCoy, Binhai Zhu · 2026
Read Optimistic Imprecise Shortest Watchtower in 1.5D and 2.5D by Bradley McCoy, Binhai Zhu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13165.txt.
Introduction
Bradley McCoy and Binhai Zhu study a watch tower task on rough ground where heights are not exact. In one form the ground is a bent line that moves in one plane, with set cross spots but loose heights. Each height must lie in a given span. In the next form the ground is a mesh of triangles in space, with set flat spots but loose heights.
The team takes the bright side view. They ask for the best tower spot when the true heights turn out as kind as they can. A watch tower must see all of the ground. Their work fits guard and sensor place tasks where ground data is coarse. It shows how to plan well when some facts are spans, not points.
Catalog record
| CREATOR | Bradley McCoy, Binhai Zhu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-13165
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimistic Imprecise Shortest Watchtower in 1.5D and 2.5D Bradley McCoy, Binhai Zhu Abstract A 1.5D imprecise terrain is an x x -monotone polyline with fixed x x -coordinates, the y y -coordinate of each vertex is not fixed but is constrained to be in a given vertical interval. A 2.5D imprecise terrain is a triangulation with fixed x x and y y -coordinates, but the z z -coordinate of each vertex is constrained to a given vertical interval. Given an imprecise terrain with n n intervals, the optimistic shortest watchtower problem asks for a terrain T T realized by a precise point in each vertical interval such that the height of the shortest vertical line segment whose lower endpoint lies on T T and upper endpoint sees the entire terrain is minimized. In this paper, we present a linear time algorithm to solve the 1.5D optimistic shortest watchtower problem exactly. For the discrete version of the 2.5D case (where the watchtower must be placed on a vertex of T T ), and we give an additive approximation scheme running in O ( O P T ε n 3 ) O(\frac{{OPT}}{\varepsilon}n^{3}) time, achieving a solution within an additive error of ε \varepsilon from the optimal solution value O P T {OPT} . 1 Introduction Placing watchtowers on polyhedral terrains is a fundamental problem in computational geometry. In practice, terrains are often constructed by surveying aircraft, which record distances to the ground. Since these measurements inevitably contain errors, the resulting data typically specifies not precise heights but intervals of possible elevations. This motivates the imprecise watchtower problem, a natural and practical extension of its classical counterpart. Imprecise terrains were introduced by Gray and Evans [ 5 ] , who showed that computing an optimistic shortest path on a 2.5D imprecise terrain is NP-hard. Since then, the problem of finding realizations of imprecise terrains with desirable properties has developed into an active research area. For a given imprecise terrain and geometric problem, one can ask for a realization that yields the best (optimistic) possible outcome, or one that yields the worst (pessimistic) outcome. Examples include approximation algorithms for minimizing turning angles in 1.5D in [ 7 ] , minimizing the number of extrema in 2.5D [ 6 ] , and water flow on 2.5D terrains [ 4 ] . More recently, Lubiw and Stround [ 12 ] studied algorithms for optimizing coplanar features, minimizing surface area, and minimizing maximum steepness. For precise terrains, guarding with a single shortest watchtower has a rich history. In 1988, Sharir [ 15 ] gave an O(n\log^{2}(n)) time algorithm for guarding a 2.5D terrain with n vertices, later improved to O(n\log n) by Zhu [ 17 ] . A shortest watchtower for a precise 1.5D terrain can be computed in linear time using the algorithm by Lee and Preparata [ 11 ] . There are two natural versions of the watchtower problem: the discrete version, where the watchtower base must be on a vertex of the terrain, and the continuous version, where it may be placed anywhere on the terrain. The results mentioned above are for the continuous version. Several other variations of guarding a precise terrain have also been studied [ 2 , 3 , 16 , 1 , 14 , 10 ] , and more recently, maximizing visibility on a 1.5D terrain with imprecise viewpoints was considered in [ 9 ] . For imprecise watchtowers, McCoy, Zhu, and Dutt [ 13 ] gave an additive PTAS for the optimistic 1.5D imprecise shortest watchtower problem. In this paper, we strengthen that result by presenting an exact linear time algorithm for the 1.5D case. We then extend our result to the discrete version of the problem in 2.5D, for which we give an additive approximation scheme running in O(\frac{{OPT}}{\varepsilon}n^{3}) time, where {OPT} is the optimal solution value of the problem. This paper is organized as follows. Section 2 provides necessary definitions. Section 3 presents our linear time algorithm for the 1.5D case. Section 4 gives details for the 2.5D case. We conclude in Section 5 with a discussion of related open problems. 2 Preliminaries A 1.5D terrain is an x -monotone polyline with n vertices. An imprecise 1.5D terrain is a 1.5D terrain where each terrain vertex comes with a closed vertical interval rather than a fixed y -coordinate. We denote these n vertical intervals \ell_{1},\ell_{2},\ldots,\ell_{n} . A realization of an imprecise terrain is obtained by selecting a y -coordinate from each interval, thereby defining a point on every \ell_{i} (see Figure 1(a) ). By slight abuse of notation, we refer to the polyline resulting from a realization as having vertices and edges , as in the precise case. For each interval \ell_{i}, let v_{i} denote the chosen vertex, and let t_{i} and b_{i} denote the top and bottom endpoints of \ell_{i} , respectively. A vertex is called left-turning if, when the polyline is traversed from left to right, it makes a left (upward) turn at that vertex. Similarly, it is right-turning if the polyline turns right (downward), and straight if it does not turn. Given a realization of an imprecise terrain T , consider the halfplanes defined by extending each edge of T and selecting the side that contains the point (0,+\infty) . The intersection of these halfplanes forms an unbounded convex polygon P, called the visibility polygon . This polygon can be computed in linear time, has O(n) vertices [ 11 ] , and in Figure 1(a) corresponds to the shaded triangle. A shortest watchtower for T is a vertical line segment \overline{uw} , where the lower endpoint u lies on T and the upper endpoint w lies on P. Two points p and q are visible if the segment \overline{pq} is above T . If every point in an edge is visible to a point we say the edge is visible, similarly for faces. If every point of T is visible from a point w, then we say that T is guarded by w. The optimistic shortest watchtower problem asks for a realization T that minimizes the length |uw| of the shortest watchtower, where u\in T and w sees all of T. (a) (b) Figure 1 : ( 1(a) ) A possible realization of a 1.5D imprecise terrain. The shaded region represents the unbounded convex polygon P . ( 1(b) ) A possible realization of a 2.5D imprecise terrain. Let Q be the simple polygon formed as follows: take the top and bottom endpoints of the intervals \ell_{i} as vertices, connect consecutive top endpoints and consecutive bottom endpoints to form two chains, and include the vertical edges \ell_{1} and \ell_{n}. The collection of shortest paths from a fixed vertex to every other vertex in a polygon can be computed in linear time [ 8 ] . Let a shortest path \pi from a point s to a point t in Q , the vertices of \pi\setminus\{s,t\} are called inner vertices . In the imprecise 2.5D terrain model , we are given n fixed x,y -coordinates together with a triangulation defined by projecting the vertices onto the xy plane. The z -coordinate of each vertex is specified only up to