Computing a geodesic two-center of points in a simple polygon. (English) Zbl 1468.68269
Summary: Given a simple polygon \(P\) with \(n\) vertices and a set \(Q\) of \(m\) points in \(P\), we consider the geodesic \(k\)-center problem where we want to find \(k\) points, called centers, in \(P\) to minimize the maximum geodesic distance of any point of \(Q\) to its closest center. In this paper, we focus on the case of \(k = 2\) and present an \(O(m(n + m) \log^3(n + m))\)-time algorithm for computing an optimal 2-center of \(Q\) with respect to the geodesic distance in \(P\).
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68W40 | Analysis of algorithms |
References:
| [1] | Ahn, H.-K.; Barba, L.; Bose, P.; De Carufel, J.-L.; Korman, M.; Oh, E., A linear-time algorithm for the geodesic center of a simple polygon, Discrete Comput. Geom., 56, 4, 836-859 (2016) · Zbl 1355.68276 |
| [2] | Aronov, B.; Fortune, S.; Wilfong, G., The furthest-site geodesic Voronoi diagram, Discrete Comput. Geom., 9, 1, 217-255 (1993) · Zbl 0770.68108 |
| [3] | Asano, T.; Toussaint, G. T., Computing Geodesic Center of a Simple Polygon (1985), McGill University, Technical Report SOCS-85.32 |
| [4] | Chan, T. M., More planar two-center algorithms, Comput. Geom., 13, 3, 189-198 (1999) · Zbl 0948.68196 |
| [5] | Chazelle, B.; Edelsbrunner, H.; Grigni, M.; Guibas, L.; Hershberger, J.; Sharir, M.; Snoeyink, J., Ray shooting in polygons using geodesic triangulations, Algorithmica, 12, 1, 54-68 (1994) · Zbl 0813.68158 |
| [6] | Chazelle, B.; Matoušek, J., On linear-time deterministic algorithms for optimization problems in fixed dimension, J. Algorithms, 21, 3, 579-597 (1996) · Zbl 0864.68040 |
| [7] | Cole, R., Slowing down sorting networks to obtain faster sorting algorithms, J. ACM, 34, 1, 200-208 (1987) · Zbl 1378.68037 |
| [8] | Cole, R., Parallel merge sort, SIAM J. Comput., 17, 4, 770-785 (1988) · Zbl 0651.68077 |
| [9] | Dyer, M. E., On a multidimensional search technique and its application to the Euclidean one-centre problem, SIAM J. Comput., 15, 3, 725-738 (1986) · Zbl 0613.68044 |
| [10] | Feder, T.; Greene, D. H., Optimal algorithms for approximate clustering, (Proc. 20th ACM Sympos. Theory Comput.. Proc. 20th ACM Sympos. Theory Comput., STOC (1988)), 434-444 |
| [11] | Guibas, L. J.; Hershberger, J., Optimal shortest path queries in a simple polygon, J. Comput. Syst. Sci., 39, 2, 126-152 (1989) · Zbl 0681.68065 |
| [12] | Halperin, D.; Sharir, M.; Goldberg, K. Y., The 2-center problem with obstacles, J. Algorithms, 42, 1, 109-134 (2002) · Zbl 0994.68185 |
| [13] | Hershberger, J., A new data structure for shortest path queries in a simple polygon, Inf. Process. Lett., 38, 5, 231-235 (1991) · Zbl 0738.68021 |
| [14] | Hwang, R.; Lee, R.; Chang, R., The slab dividing approach to solve the Euclidean \(p\)-center problem, Algorithmica, 9, 1, 1-22 (1993) · Zbl 0766.68136 |
| [15] | Megiddo, N., Linear-time algorithms for linear programming in \(R^3\) and related problems, SIAM J. Comput., 12, 4, 759-776 (1983) · Zbl 0521.68034 |
| [16] | Oh, E.; De Carufel, J.-L.; Ahn, H.-K., The 2-center problem in a simple polygon, (Proc. 26th Int. Sympos. Algo. Comput.. Proc. 26th Int. Sympos. Algo. Comput., ISAAC (2015)), 307-317 · Zbl 1472.68207 |
| [17] | Papadopoulou, E.; Lee, D. T., A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains, Algorithmica, 20, 4, 319-352 (1998) · Zbl 0895.68137 |
| [18] | 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 |
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.
