Abstract
Guarding polyhedral terrains is a fundamental problem with realistic applications. In this paper we study three such problems when the terrains are precise and imprecise respectively. The first problem we consider is to place a segment pq with a fixed length over a precise input terrain T with n vertices in 2D (resp. 3D), such that pq can see every point on T and the maximum y-coordinate (resp. z-coordinate) of p and q is minimized. For terrains in 2D and 3D we present algorithms running in O(n) and \(O(n^3\log n)\) time respectively. The second problem is to place two horizontal segments \(p_1q_1\) and \(p_2q_2\) of a fixed length and with the minimum y-coordinate to cover a 2D terrain (x-monotone chain), which we solve in \(O(n^2\log n)\) time.
Given a polyhedral terrain T of n vertices in 3D, a shortest watchtower is a vertical segment erected on T such that every point on T is visible from the top of the segment and the length of the segment is minimized. The problem was solved in \(O(n\log n)\) time more than 30 years ago. In this paper, we investigate the problem under the imprecise model where each vertex of T is on a given vertical interval. We show that when the location of a watchtower is fixed, the problem in 2D and 3D can be solved with linear programming, which leads to an additive \(\varepsilon \)-approximation for the general problem. We implement this algorithm using CPLEX which demonstrate the efficiency and accuracy of the algorithm when \(n\le 100\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agarwal, P.K., et al.: Guarding a terrain by two watchtowers. Algorithmica 58(2), 352–390 (2010)
Bespamyatnikh, S., Chen, Z., Wang, K., Zhu, B.: On the planar two-watchtower problem. In: Wang, J. (ed.) COCOON 2001. LNCS, vol. 2108, pp. 121–130. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44679-6_14
Bhattacharya, B.K., Czyzowicz, J., Egyed, P., Toussaint, G.T., Stojmenovic, I., Urrutia, J.: Computing shortest transversals of sets. Int. J. Comput. Geom. Appl. 2(4), 417–442 (1992)
Bose, P., Shermer, T.C., Toussaint, G.T., Zhu, B.: Guarding polyhedral terrains. Comput. Geom. Theo. Appl. 7, 173–185 (1997)
Cole, R., Sharir, M.: Visibility problems for polyhedral terrains. J. Symb. Comput. 7(1), 11–30 (1989)
Driemel, A., Haverkort, H.J., Löffler, M., Silveira, R.I.: Flow computations on imprecise terrains. J. Comput. Geom. 4(1), 38–78 (2013)
Duraisamy, N., et al.: Half-guarding weakly-visible polygons and terrains. In: Dawar, A., Guruswami, V., editors, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’2022), December 18–20, 2022, IIT Madras, Chennai, India, volume 250 of LIPIcs, pp. 18:1–18:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
Gray, C., Evans, W.S.: Optimistic shortest paths on uncertain terrains. In: Proceedings of the 16th Canadian Conference on Computational Geometry (CCCG’2004), Concordia University, Montréal, Québec, Canada, August 9–11, 2004, pp. 68–71 (2004)
Gray, C., Kammer, F., Löffler, M., Silveira, R.I.: Removing local extrema from imprecise terrains. Comput. Geom. Theo. Appl. 45(7), 334–349 (2012)
Gray, C., Löffler, M., Silveira, R.I.: Smoothing imprecise 1.5d terrains. Int. J. Comput. Geom. Appl. 20(4), 381–414 (2010)
Katoh, N., Wang, W., Yinfeng, X., Zhu, B.: Parametric search: three new applications. Front. Math. China 5(2), 65–73 (2010)
Lee, D.T., Preparata, F.P.: An optimal algorithm for finding the kernel of a polygon. J. ACM 26(3), 415–421 (1979)
Lubiw, A., Stroud, G.: Computing realistic terrains from imprecise elevations. In: Y. Bahoo., Georgiou, K., editors, Proceedings of the 34th Canadian Conference on Computational Geometry, (CCCG’2022), Toronto Metropolitan University, Toronto, Ontario, Canada, August 25–27, 2022, pp. 227–234 (2022)
Preparata, F.P., Muller, D.E.: Finding the intersection of n half-spaces in time O(n log n). Theor. Comput. Sci. 8, 45–55 (1979)
Seth, R., Maheshwari, A., Nandy, S.C.: Acrophobic guard watchtower problem. Comput. Geom. Theo. Appl. 109, 101918 (2023)
Sharir, M.: The shortest watchtower and related problems for polyhedral terrains. Inf. Process. Lett. 29(5), 265–270 (1988)
Tripathi, N., Pal, M., De, M., Das, G., Nandy, S.C.: Guarding polyhedral terrain by k-watchtowers. In: Chen, J., Lu, P. (eds.) FAW 2018. LNCS, vol. 10823, pp. 112–125. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78455-7_9
Vaidya, P.M.: Speeding-up linear programming using fast matrix multiplication (extended abstract). In: 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pp. 332–337. IEEE Computer Society (1989)
Wang, C., Zhu, B.: Three dimensional weak visibility: complexity and algorithms. Theor. Comput. Sci. 234(1–2), 219–232 (2000)
Zhu, B.: Improved algorithms for computing the shortest watchtower of polyhedral terrains. In: Proceedings of the 3rd Canadian Conference on Computational Geometry (CCCG’1992), St. John’s, Newfoundland, Canada, August 1992, pp. 286–291. Memorial University of Newfoundland (1992)
Zhu, B.: Computing the shortest watchtower of a polyhedral terrain in O(n log n) time. Comput. Geom. Theo. Appl. 8, 181–193 (1997)
Acknowledgments
This research is supported by NSF under grant CNS-2243010.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
McCoy, B., Zhu, B., Dutt, A. (2024). Guarding Precise and Imprecise Polyhedral Terrains with Segments. In: Wu, W., Guo, J. (eds) Combinatorial Optimization and Applications. COCOA 2023. Lecture Notes in Computer Science, vol 14462. Springer, Cham. https://doi.org/10.1007/978-3-031-49614-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-49614-1_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-49613-4
Online ISBN: 978-3-031-49614-1
eBook Packages: Computer ScienceComputer Science (R0)