Abstract
In this paper we study the problem of finding \(K\) shortest non crossing paths for unit disks in a polygonal domain with static obstacles. These paths are called thick paths. In this problem the terminals are located on the boundary of a polygon with holes. The problem is introduced by Mitchell and Polischuk. They presented an algorithm that computes the paths. We present a new algorithm for finding the paths. The time complexity is better in some cases. We also study the problem in the case where at most one terminal of each path can lie on hole boundaries. We present feasibility conditions and an algorithm to find a set of feasible thick paths.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arkin, E.M., Mitchell, J.S.B., Polishchuk, V.: Maximum thick paths in static and dynamic environments. Comput. Geom. Theory Appl. 43(3), 279–294 (2010)
Bastert, O., Fekete, S.P.: Geometric wire routing. In: Technical Report No. 332, Zentrum fuer Angewandte Informatik (1998)
Duncan, C.A., Efrat, A., Kobourov, S.G., Wenk, C.: Drawing with fat edges. In: GD01, Revised Papers from the 9th International Symposium on Graph Drawing, London. Springer-Verlag, New York, pp. 162–177 (2002)
Efrat, A., Kobourov, S., Stepp, M., Wenk, C.: Growing fat graphs. In: SCG 02: Proceedings of the 18th Annual Symposium on Computational Geometry. ACM Press, New York, pp. 277–278 (2002)
Erickson, J., Nayyer, A.: Shortest non-crossing walks in the plane. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2011)
Kim, J., Mitchell, J.S.B., Polishchuk, V., Yang, S., Zou, J.: Routing multi-class traffic flows in the plane. Comput. Geom. Theory Appl. 45(3), 99–114 (2012)
Melissaratos, E.A., Souvaine, D.L.: On solving geometric optimization problems using shortest paths. In: Proceedings of the 6th Annual ACM Symposium on Computational Geometry, pp. 350–359 (1990)
Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 633–701. Elsevier Science B.V., North-Holland (2000)
Mitchell, J.S.B., Polishchuk, V.: Thick non-crossing paths and minimum-cost flows in polygonal domains. In: 23rd ACM Symposium on Computational Geometry, pp. 56–65 (2007)
Papadopoulou, E.: K-pairs non-crossing shortest paths in a simple polygon. Comput. Geom. Appl. 9(6), 533–552 (1999)
Polishchuk, V.: Thick non-crossing paths and minimum-cost flows in polygonal domains. Ph.D. thesis, Stony Brook University (2007)
Takahashi, J., Suzuki, H., Nishizeki, T.: Algorithms for finding non-crossing paths with minimum total length in plane graphs. In: ISAAC, pp. 400–409 (1992)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tahmasbi, M., Mirehi, N. Thick non-crossing paths in a polygonal domain. Optim Lett 9, 743–753 (2015). https://doi.org/10.1007/s11590-014-0776-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-014-0776-0