The Geodesic $2$-center Problem in a Simple Polygon
Preprint
Abstract
The geodesic $k$-center problem in a simple polygon with $n$ vertices consists in the following. Find a set $S$ of $k$ points in the polygon that minimizes the maximum geodesic distance from any point of the polygon to its closest point in $S$. In this paper, we focus on the case where $k=2$ and present an exact algorithm that returns a geodesic $2$-center in $O(n^2\log^2 n)$ time.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- A Linear-Time Algorithm for the Geodesic Center of a Simple PolygonDiscrete & Computational Geometry, 2016
- GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGONInternational Journal of Computational Geometry & Applications, 2011
- More planar two-center algorithmsComputational Geometry, 1999
- The slab dividing approach to solve the EuclideanP-Center problemAlgorithmica, 1993
- On the ball spanned by ballsDiscrete & Computational Geometry, 1989
- Computing the geodesic center of a simple polygonDiscrete & Computational Geometry, 1989
- Parallel Merge SortSIAM Journal on Computing, 1988
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygonsAlgorithmica, 1987
- Computing the Geodesic Center of a Simple Polygon1987
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related ProblemsSIAM Journal on Computing, 1983