×
Ahn, Hee-Kap; Barba, Luis; Bose, Prosenjit; De Carufel, Jean-Lou; Korman, Matias; Oh, Eunjin

A linear-time algorithm for the geodesic center of a simple polygon. (English) Zbl 1355.68276

Discrete Comput. Geom. 56, No. 4, 836-859 (2016).
Summary: Let \(P\) be a closed simple polygon with \(n\) vertices. For any two points in \(P\), the geodesic distance between them is the length of the shortest path that connects them among all paths contained in \(P\). The geodesic center of \(P\) is the unique point in \(P\) that minimizes the largest geodesic distance to all other points of \(P\). In [Discrete Comput. Geom. 4, No. 6, 611–626 (1989; Zbl 0689.68067)], R. Pollack et al. showed an \(O(n\log n)\)-time algorithm that computes the geodesic center of \(P\). Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem.

Cited in 1 Review
Cited in 16 Documents

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity

Keywords:

geodesic distance; facility location; simple polygons

Citations:

Zbl 0689.68067
Cite Review PDF
Full Text: DOI arXiv Link

References:

[1] Aronov, B.: On the geodesic Voronoi diagram of point sites in a simple polygon. Algorithmica 4(1-4), 109-140 (1989) · Zbl 0664.68043 · doi:10.1007/BF01553882
[2] Aronov, B., Fortune, S., Wilfong, G.: The furthest-site geodesic Voronoi diagram. Discrete Comput. Geom. 9(1), 217-255 (1993) · Zbl 0770.68108 · doi:10.1007/BF02189321
[3] Asano, T., Toussaint, G.: Computing the geodesic center of a simple polygon. Technical Report SOCS-85.32, McGill University (1985) · Zbl 0644.68072
[4] Bae, S.W., Korman, M., Mitchell, J.S.B., Okamoto, Y., Polishchuk, V., Wang, H.: Computing the L1 geodesic diameter and center of a polygonal domain. In: Ollinger, N., Vollmer, H. (eds) 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 47, pp. 14:1-14:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2016). ISBN 978-3-95977-001-9 · Zbl 1388.68280
[5] Bae, S.W., Korman, M., Okamoto, Y.: The geodesic diameter of polygonal domains. Discrete Comput. Geom. 50(2), 306-329 (2013) · Zbl 1298.52013 · doi:10.1007/s00454-013-9527-8
[6] Bae, S.W., Korman, M., Okamoto, Y.: Computing the geodesic centers of a polygonal domain. In: Computational Geometry: Theory and Applications. Special issue of selected papers from the 26th Canadian Conference on Computational Geometry (CCCG’14) (2015) (in press) · Zbl 1287.68166
[7] Bae, S.W., Korman, M., Okamoto, Y., Wang, H.: Computing the \[{L}_1\] L1 geodesic diameter and center of a simple polygon in linear time. Comput. Geom. 48(6), 495-505 (2015) · Zbl 1318.65011 · doi:10.1016/j.comgeo.2015.02.005
[8] Chazelle B.: A theorem on polygon cutting with applications. In: Proceedings of FOCS, pp. 339-349 (1982) · Zbl 0642.68081
[9] Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6(1), 485-524 (1991) · Zbl 0753.68090 · doi:10.1007/BF02574703
[10] Djidjev, H., Lingas, A., Sack, J.-R.: An \[O(n\log n)O\](nlogn) algorithm for computing the link center of a simple polygon. Discrete Comput. Geom. 8, 131-152 (1992) · Zbl 0776.68108 · doi:10.1007/BF02293040
[11] Edelsbrunner, H., Mücke, E.P.: Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9(1), 66-104 (1990) · Zbl 0732.68099 · doi:10.1145/77635.77639
[12] 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) · Zbl 0642.68081 · doi:10.1007/BF01840360
[13] Harborth, H., Möller, M.: The Esther-Klein-problem in the projective plane. Inst. Mathematik, TU Braunschweig (1993) · Zbl 0807.51008
[14] Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338-355 (1984) · Zbl 0535.68022 · doi:10.1137/0213024
[15] Hershberger, J., Suri, S.: Matrix searching with the shortest-path metric. SIAM J. Comput. 26(6), 1612-1634 (1997) · Zbl 0885.68086 · doi:10.1137/S0097539793253577
[16] Ke, Y.: An efficient algorithm for link-distance problems. In: Proceedings of the Fifth Annual Symposium on Computational Geometry, pp. 69-78. ACM, Saarbrücken (1989) · Zbl 0732.68099
[17] Lee, D.-T., Preparata, F.P.: Euclidean shortest paths in the presence of rectilinear barriers. Networks 14(3), 393-410 (1984) · Zbl 0545.90098 · doi:10.1002/net.3230140304
[18] Matoušek, J.: Approximations and optimal geometric divide-and-conquer. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 505-511. ACM, New York (1991) · Zbl 0664.68043
[19] Matoušek, J.: Approximations and optimal geometric divide-and-conquer. J. Comput. Syst. Sci. 50(2), 203-208 (1995) · Zbl 0827.68048 · doi:10.1006/jcss.1995.1018
[20] Matoušek, J.: Lectures on Discrete Geometry, Graduate Texts in Math, vol. 212. Springer, New York (2002) · Zbl 0999.52006
[21] Megiddo, N.: On the ball spanned by balls. Discrete Comput. Geom. 4(1), 605-610 (1989) · Zbl 0688.90020 · doi:10.1007/BF02187750
[22] Mitchell, JSB; Sack, JR (ed.); Urrutia, J. (ed.), Geometric shortest paths and network optimization, 633-701 (2000), Amsterdam · Zbl 0941.68137 · doi:10.1016/B978-044482537-7/50016-4
[23] Nilsoon, B.J., Schuierer, S.: Computing the rectilinear link diameter of a polygon. In: Computational Geometry—Methods, Algorithms and Applications, pp. 203-215. Springer, Berlin (1991) · Zbl 0788.68145
[24] Nilsoon, B.J., Schuierer, S.: An optimal algorithm for the rectilinear link center of a rectilinear polygon. Comput. Geom. 6, 169-194 (1996) · Zbl 0849.68128 · doi:10.1016/0925-7721(95)00026-7
[25] Pollack, R., Sharir, M., Rote, G.: Computing the geodesic center of a simple polygon. Discrete Comput. Geom. 4(1), 611-626 (1989) · Zbl 0689.68067 · doi:10.1007/BF02187751
[26] Suri, S.: Minimum link paths in polygons and related problems. PhD Thesis, Johns Hopkins University (1987)
[27] Suri, S.: Computing geodesic furthest neighbors in simple polygons. J. Comput. Syst. Sci. 39(2), 220-235 (1989) · Zbl 0679.68100 · doi:10.1016/0022-0000(89)90045-7
[28] Turán, P.: On an extremal problem in graph theory. Matematikai és Fizikai Lapok 48(436-452), 137 (1941) · JFM 67.0732.03
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.