scientific article; zbMATH DE number 4051002
[For the entire collection see Zbl 0636.00011.] The authors present a polynomial-time algorithm for finding the geodesic center of a simple polygon, which is defined to be a point in the polygon whose greatest internal distance to any other point in the polygon is a minimum. The distance between two points in a simple polygon is measured as the length of the shortest internal path between them. The key idea is the construction of a geodesic farthest-point Voronoi diagram for a simple polygon which consists of straight lines and hyperbolic curve segments. The geodesic center of a simple polygon is either the center of its geodesic diameter or a vertex of the Voronoi diagram. The algorithm runs in O(n 3 log log n) time, n being the number of vertices of the given polygon.
- Computing the link center of a simple polygon
- The furthest-site geodesic Voronoi diagram
- The geodesic 2-center problem in a simple polygon
- Computing the geodesic centers of a polygonal domain
- Multiple-guard kernels of simple polygons
- Computing geodesic furthest neighbors in simple polygons
- The polygon burning problem
- The geodesic farthest-point Voronoi diagram in a simple polygon
- Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
- Computing a maxian point of a simple rectilinear polygon
- Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications.
- On the central path problem
- Geodesic Fréchet distance inside a simple polygon
- The geodesic diameter of polygonal domains
- On the central path problem
- Computing the center of area of a polygon
- scientific article; zbMATH DE number 597698 (Why is no real title available?)
- Matrix Searching with the Shortest-Path Metric
- On the geodesic centers of polygonal domains
- Geodesic disks and clustering in a simple polygon
- Geodesic center of a simple polygon using a logarithmic number of extra variables
- Computing the \(L_1\) geodesic diameter and center of a polygonal domain
- scientific article; zbMATH DE number 6789192 (Why is no real title available?)
- Constrained geodesic centers of a simple polygon
- Geodesic Disks and Clustering in a Simple Polygon
- Computing the geodesic center of a simple polygon
- The Visibility Center of a Simple Polygon
- An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
- Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
- The geodesic edge center of a simple polygon
- Point selections from Jordan domains in Riemannian surfaces
- A linear-time algorithm for the geodesic center of a simple polygon
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787491)