×

Approximate shortest paths in polygons with violations. (English) Zbl 1458.68266

Summary: We study the shortest \(k\)-violation path problem in a simple polygon. Let \(P\) be a simple polygon in \(\mathbb{R}^2\) with \(n\) vertices and let \(s,t\) be a pair of points in \(P\). Let \(\operatorname{int}(P)\) represent the interior of \(P\). Let \(\widetilde{P}= \mathbb{R}^2\setminus\operatorname{int}(P)\) represent the exterior of \(P\). For an integer \(k\geq 0\), the shortest \(k\)-violation path problem in \(P\) is the problem of computing the shortest path from \(s\) to \(t\) in \(P\), such that at most \(k\) path segments are allowed to be in \(\widetilde{P}\). The subpaths of a \(k\)-violation path are not allowed to bend in \(\widetilde{P}\). For any \(k\), we present a \((1+2\epsilon)\) factor approximation algorithm for the problem that runs in \(O( n^2 \sigma^2k\log n^2 \sigma^2+ n^2 \sigma^2k)\) time. Here \(\sigma=O( \log_\delta(\frac{ L}{ r}))\) and \(\delta\), \(L\), \(r\) are geometric parameters.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
68W25 Approximation algorithms

Software:

BUSHWHACK
Full Text: DOI

References:

[1] Agarwal, P. K., Kumar, N., Sintos, S. and Suri, S., Computing shortest paths in the plane with removable obstacles. In: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018). · Zbl 1477.68454
[2] Aleksandrov, L., Lanthier, M., Maheshwari, A. and Sack, J. R., An \(\varepsilon\) approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Scandinavian Workshop on Algorithm Theory, pp. 11-22, (Springer, 1998). · Zbl 1504.68243
[3] Asano, T., Asano, T., Guibas, L., Hershberger, J. and Imai, H., Visibility-polygon search and euclidean shortest paths. In: 26th annual symposium on Foundations of Computer Science, pp. 155-164 (IEEE, 1985).
[4] Chazelle, B., Triangulating a simple polygon in linear time, Discret. Comput. Geom.6 (1991) 485-524. · Zbl 0753.68090
[5] Cheng, S. W. and Jin, J., Approximate shortest descending paths, SIAM Journal on Computing43(2) (2014) 410-428. · Zbl 1298.65031
[6] Cheng, S. W., Na, H. S., Vigneron, A. and Wang, Y., Approximate shortest paths in anisotropic regions, SIAM Journal on Computing38(3) (2008) 802-824. · Zbl 1187.68636
[7] Ghosh, S. K., Visibility algorithms in the plane (Cambridge University Press, 2007). · Zbl 1149.68076
[8] Ghosh, S. K. and Mount, D. M., An output-sensitive algorithm for computing visibility graphs, SIAM Journal on Computing20(5) (1991) 888-910. · Zbl 0768.68202
[9] Guibas, L., Hershberger, J., Leven, D., Sharir, M. and Tarjan, R. E., Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica2(1-4) (1987) 209-233. · Zbl 0642.68081
[10] Hershberger, J., Kumar, N. and Suri, S., Shortest paths in the plane with obstacle violations. In: 25th Annual European Symposium on Algorithms (ESA 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017). · Zbl 1442.68251
[11] Hershberger, J. and Suri, S., Practical methods for approximating shortest paths on a convex polytope in \(\mathcal{R}^3\), Computational Geometry10(1) (1998) 31-46. · Zbl 0896.68140
[12] Hershberger, J. and Suri, S., An optimal algorithm for euclidean shortest paths in the plane, SIAM Journal on Computing28(6) (1999) 2215-2256. · Zbl 0939.68157
[13] Kapoor, S. and Maheshwari, S., Efficient algorithms for euclidean shortest path and visibility problems with polygonal obstacles. In: Proceedings of the fourth annual symposium on Computational geometry, pp. 172-182 (ACM, 1988).
[14] Lanthier, M., Maheshwari, A. and Sack, J. R., Approximating weighted shortest paths on polyhedral surfaces. In: Proceedings of the Thirteenth Annual Symposium on Computational Geometry, pp. 274-283 (ACM, 1997). · Zbl 0973.90084
[15] Li, F. and Klette, R., Euclidean shortest paths. In: Euclidean Shortest Paths, pp. 3-29 (Springer, 2011). · Zbl 1263.68008
[16] Maheshwari, A., Nandy, S. C., Pattanayak, D., Roy, S. and Smid, M., Geometric path problems with violations, Algorithmica80(2) (2018) 448-471. · Zbl 1383.68093
[17] Mitchell, J. S., A new algorithm for shortest paths among obstacles in the plane, Annals of Mathematics and Artificial Intelligence3(1), 83-105 (1991). · Zbl 0875.68765
[18] Mitchell, J. S., Shortest paths among obstacles in the plane, International Journal of Computational Geometry & Applications6(3) 309-332 (1996). · Zbl 0860.68109
[19] Mitchell, J. S., Geometric shortest paths and network optimization, Handbook of Computational Geometry334633-702 (2000).
[20] Overmars, M. H. and Welzl, E., New methods for computing visibility graphs. In: Proceedings of the fourth annual symposium on Computational geometry, pp. 164-171 (ACM, 1988).
[21] Rohnert, H., Shortest paths in the plane with convex polygonal obstacles, Information Processing Letters23(2) (1986) 71-76. · Zbl 0607.68052
[22] S. Roy, S. Lodha, S. Das and A. Maheswari, Approximate shortest descent path on a terrain (2007).
[23] Snoeyink, J. H. J., Computing minimum length paths of a given homotopy class. In: Comput. Geom. Theory Appl. (Citeseer, 1990). · Zbl 0815.68116
[24] Storer, J. A. and Reif, J. H., Shortest paths in the plane with polygonal obstacles, Journal of the ACM (JACM)41(5) (1994) 982-1012. · Zbl 0814.68129
[25] Sun, Z. and Reif, J., Bushwhack: An approximation algorithm for minimal paths through pseudo-euclidean spaces. In: International Symposium on Algorithms and Computation, pp. 160-171 (Springer, 2001). · Zbl 1077.68917
[26] Toussaint, G. T., The erdös-nagy theorem and its ramifications. In: Proceedings of the 11th Canadian Conference on Computational Geometry, UBC, Vancouver, British Columbia, Canada, , August 15-18, (1999). · Zbl 1081.65024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.