Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Geodesics in global differential geometry (53C22) Variational problems in applications to the theory of geodesics (problems in one independent variable) (58E10)
Abstract: This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as known by Hershberger and Suri. For general polygonal domains with h >= 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n^7 (log n + h)). The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.
Recommendations
Cites work
- scientific article; zbMATH DE number 4051002 (Why is no real title available?)
- scientific article; zbMATH DE number 1305410 (Why is no real title available?)
- scientific article; zbMATH DE number 2107521 (Why is no real title available?)
- An Optimal Algorithm for Euclidean Shortest Paths in the Plane
- An isoperimetric problem for tetrahedra
- Computing the geodesic center of a simple polygon
- Matrix Searching with the Shortest-Path Metric
- Optimal shortest path queries in a simple polygon
- Querying two boundary points for shortest paths in a polygonal domain
- SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
- Shortest Path Problems on a Polyhedral Surface
- Shortest Path Queries in Polygonal Domains
- Star Unfolding of a Polytope with Applications
- The furthest-site geodesic Voronoi diagram
- The geodesic diameter of polygonal domains
- The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
Cited in
(17)- Maximal distortion of geodesic diameters in polygonal domains
- On the polygonal diameter (= link diameter) of the interior, resp. exterior, of a simple closed polygon in the plane
- Rectilinear link diameter and radius in a rectilinear polygonal domain
- Computing the external geodesic diameter of a simple polygon
- Convex hulls in polygonal domains
- A linear-time algorithm for the geodesic center of a simple polygon
- Computing the \(L_1\) geodesic diameter and center of a polygonal domain
- Rounding corners of gearlike domains and the omitted area problem
- An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
- Rectilinear link diameter and radius in a rectilinear polygonal domain
- The geodesic diameter of polygonal domains
- Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
- scientific article; zbMATH DE number 7030514 (Why is no real title available?)
- Computing the geodesic centers of a polygonal domain
- The size of spanning disks for polygonal curves
- Computing a minimum-width cubic and hypercubic shell
- Computing the \(L_1\) geodesic diameter and center of a polygonal domain
This page was built for publication: The geodesic diameter of polygonal domains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q368771)
