Abstract
We study the problem of computing shortest k-violation path problem on polygons. 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 int(P) represent the interior of P. In other words, \(int(P) = P \setminus \varDelta (P)\), where \(\varDelta (P)\) is the boundary of P. Let \(\tilde{P}=\mathbb {R}^2 \setminus int(P)\) represent the exterior of P. For an integer \(k \ge 0\), the problem of k-violation shortest path 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 \(\tilde{P}\). The path segments are not allowed to bend in \(\tilde{P}\). For any k, we present a \((1+\epsilon )\) factor approximation algorithm for the problem, that runs in \(O(n^2 \sigma ^2 k\log n^2 \sigma ^2 + n^2 \sigma ^2 k)\) time. Here \(\sigma =O( \log _\delta (\frac{|L|}{r}))\) and \(\delta \), L, r are geometric parameters.
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., Kumar, N., Sintos, S., 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)
Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.-R.: An \(\varepsilon \)—approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Arnborg, S., Ivansson, L. (eds.) SWAT 1998. LNCS, vol. 1432, pp. 11–22. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054351
Asano, T., Asano, T., Guibas, L., Hershberger, J., Imai, H.: Visibility-polygon search and Euclidean shortest paths. In: 26th Annual Symposium on Foundations of Computer Science, pp. 155–164. IEEE (1985)
Cheng, S.W., Na, H.S., Vigneron, A., Wang, Y.: Approximate shortest paths in anisotropic regions. SIAM J. Comput. 38(3), 802–824 (2008)
Ghosh, S.K.: Visibility Algorithms in the Plane. Cambridge University Press, Cambridge (2007)
Ghosh, S.K., Mount, D.M.: An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput. 20(5), 888–910 (1991)
Guibas, L., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2(1–4), 209–233 (1987)
Hershberger, J., Kumar, N., 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)
Hershberger, J., Suri, S.: Practical methods for approximating shortest paths on a convex polytope in \(\cal{R}^3\). Comput. Geom. 10(1), 31–46 (1998)
Hershberger, J., Suri, S.: An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput. 28(6), 2215–2256 (1999)
Kapoor, S., 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)
Lanthier, M., Maheshwari, A., 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)
Li, F., Klette, R.: Euclidean shortest paths. In: Li, F., Klette, R. (eds.) Euclidean Shortest Paths, pp. 3–29. Springer, London (2011). https://doi.org/10.1007/978-1-4471-2256-2_1
Maheshwari, A., Nandy, S.C., Pattanayak, D., Roy, S., Smid, M.: Geometric path problems with violations. Algorithmica 80(2), 448–471 (2018)
Mitchell, J.S.: A new algorithm for shortest paths among obstacles in the plane. Ann. Math. Artif. Intell. 3(1), 83–105 (1991)
Mitchell, J.S.: Shortest paths among obstacles in the plane. Int. J. Comput. Geom. Appl. 6(03), 309–332 (1996)
Mitchell, J.S.: Geometric shortest paths and network optimization. In: Handbook of Computational Geometry, vol. 334, pp. 633–702 (2000)
Overmars, M.H., Welzl, E.: New methods for computing visibility graphs. In: Proceedings of the Fourth Annual Symposium on Computational Geometry, pp. 164–171. ACM (1988)
Rohnert, H.: Shortest paths in the plane with convex polygonal obstacles. Inf. Process. Lett. 23(2), 71–76 (1986)
Roy, S., Lodha, S., Das, S., Maheswari, A.: Approximate shortest descent path on a terrain (2007)
Snoeyink, J.H.J.: Computing minimum length paths of a given homotopy class. In: Computational Geometry: Theory and Applications. Citeseer (1990)
Storer, J.A., Reif, J.H.: Shortest paths in the plane with polygonal obstacles. J. ACM (JACM) 41(5), 982–1012 (1994)
Sun, Z., Reif, J.: BUSHWHACK: an approximation algorithm for minimal paths through pseudo-Euclidean spaces. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol. 2223, pp. 160–171. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45678-3_15
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Dutta, B., Roy, S. (2019). Approximate Shortest Paths in Polygons with Violations. In: Li, Y., Cardei, M., Huang, Y. (eds) Combinatorial Optimization and Applications. COCOA 2019. Lecture Notes in Computer Science(), vol 11949. Springer, Cham. https://doi.org/10.1007/978-3-030-36412-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-36412-0_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-36411-3
Online ISBN: 978-3-030-36412-0
eBook Packages: Computer ScienceComputer Science (R0)