LIPIcs.ISAAC.2016.14.pdf
- Filesize: 0.58 MB
- 12 pages
Document
L_1 Geodesic Farthest Neighbors in a Simple Polygon and Related Problems
Author
-
Part of:
Volume:
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-12-07
Cite As Get BibTex
Sang Won Bae. L_1 Geodesic Farthest Neighbors in a Simple Polygon and Related Problems. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.14
Abstract
In this paper, we investigate the L_1 geodesic farthest neighbors in a simple polygon P, and address several fundamental problems related to farthest neighbors. Given a subset S subseteq P, an L_1 geodesic farthest neighbor of p in P from S is one that maximizes the length of L_1 shortest path from p in P. Our list of problems include: computing the diameter, radius, center, farthest-neighbor Voronoi diagram, and two-center of S under the L_1 geodesic distance. We show that all these problems can be solved in linear or near-linear time based on our new observations on farthest neighbors and extreme points. Among them, the key observation shows that there are at most four extreme points of any compact subset S subseteq P with respect to the L_1 geodesic distance after removing redundancy.
Subject Classification
Keywords
- simple polygon
- L_1 geodesic distance
- farthest neighbor
- farthest-neighbor Voronoi diagram
- k-center
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
H.-K. Ahn, L. Barba, P. Bose, J.-L. De Carufel, M. Korman, and E. Oh. A linear-time algorithm for the geodesic center of a simple polygon. In Proc. 31st Symp. Comput. Geom. (SoCG 2015), volume 34 of LIPIcs, pages 209-223, 2015.
-
B. Aronov, S. Fortune, and G. Wilfong. The furthest-site geodesic Voronoi diagram. Discrete Comput. Geom., 9:217-255, 1993.
-
S.W. Bae, M. Korman, Y. Okamoto, and H. Wang. Computing the L₁ geodesic diameter and center of a simple polygon in linear time. Comput. Geom., 48(6):495-505, 2015.
-
T. M. Chan. More planar two-center algorithms. Comput. Geom., 13(3):189-198, 1999.
-
Z. Drezner. On the rectangular p-center problem. Naval Research Logistics (NRL), 34(2):229-234, 1987.
-
L. J. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126-152, 1989.
-
L. J. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. Tarjan. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987.
-
J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Comput. Geom., 4(2):63-97, 1994.
-
J. Hershberger and S. Suri. Matrix searching with the shortest path metric. SIAM J. Comput., 26(6):1612-1634, 1997.
-
E. Oh, S.W. Bae, and H.-K. Ahn. Computing a geodesic two-center of points in a simple polygon. In Proc. 12th Latin American Theoretical Info. Symp. (LATIN 2016), volume 9644 of LNCS, pages 646-658, 2016.
-
E. Oh, L. Barba, and H.-K. Ahn. The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon. In Proc. 32nd Symp. Comput. Geom. (SoCG 2016), LIPIcs, pages 56:1-56:15, 2016.
-
E. Oh, J.-L. De Carufel, and H.-K. Ahn. The 2-center problem in a simple polygon. In Proc. 26th Int'l Symp. Algo. Comput. (ISAAC 2015), volume 9472 of LNCS, pages 307-317, 2015.
-
G. T. Toussaint. Computing geodesic properties inside a simple polygon. Revue D'Intelligence Artificielle, 3:9-42, 1989.