Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2601.13165 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915739140620288 |
|---|---|
| author | McCoy, Bradley Zhu, Binhai |
| author_facet | McCoy, Bradley Zhu, Binhai |
| contents | A 1.5D imprecise terrain is an $x$-monotone polyline with fixed $x$-coordinates, the $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$ and $y$-coordinates, but the $z$-coordinate of each vertex is constrained to a given vertical interval. Given an imprecise terrain with $n$ intervals, the optimistic shortest watchtower problem asks for a terrain $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$ 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$), and we give an additive approximation scheme running in $O(\frac{OPT}{\varepsilon}n^3)$ time, achieving a solution within an additive error of $\varepsilon$ from the optimal solution value ${OPT}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_13165 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimistic Imprecise Shortest Watchtower in 1.5D and 2.5D McCoy, Bradley Zhu, Binhai Computational Geometry A 1.5D imprecise terrain is an $x$-monotone polyline with fixed $x$-coordinates, the $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$ and $y$-coordinates, but the $z$-coordinate of each vertex is constrained to a given vertical interval. Given an imprecise terrain with $n$ intervals, the optimistic shortest watchtower problem asks for a terrain $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$ 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$), and we give an additive approximation scheme running in $O(\frac{OPT}{\varepsilon}n^3)$ time, achieving a solution within an additive error of $\varepsilon$ from the optimal solution value ${OPT}$. |
| title | Optimistic Imprecise Shortest Watchtower in 1.5D and 2.5D |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2601.13165 |