The geodesic diameter of polygonal domains

DOI10.1007/S00454-013-9527-8zbMATH Open1298.52013arXiv1001.0695OpenAlexW2569574600MaRDI QIDQ368771FDOQ368771

Authors: Sang Won Bae, Matias Korman, Yoshio Okamoto 

Publication date: 23 September 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1001.0695

Recommendations

• The geodesic diameter of polygonal domains
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Computing the geodesic centers of a polygonal domain
• scientific article; zbMATH DE number 7030514

zbMATH Keywords

convex functionexact algorithmshortest pathgeodesic diameterlower envelopepolygonal domain

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• The furthest-site geodesic Voronoi diagram
• Optimal shortest path queries in a simple polygon
• An isoperimetric problem for tetrahedra
• Shortest Path Problems on a Polyhedral Surface
• Shortest Path Queries in Polygonal Domains
• The geodesic diameter of polygonal domains
• Title not available (Why is that?)
• Querying two boundary points for shortest paths in a polygonal domain
• Title not available (Why is that?)
• Star Unfolding of a Polytope with Applications
• Matrix Searching with the Shortest-Path Metric
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
• Computing the geodesic center of a simple polygon

Cited In (17)

• Rectilinear link diameter and radius in a rectilinear polygonal domain
• The size of spanning disks for polygonal curves
• Computing the geodesic centers of a polygonal domain
• Computing the external geodesic diameter of a simple polygon
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• A linear-time algorithm for the geodesic center of a simple polygon
• Rounding corners of gearlike domains and the omitted area problem
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Convex hulls in polygonal domains
• Rectilinear link diameter and radius in a rectilinear polygonal domain
• On the polygonal diameter (= link diameter) of the interior, resp. exterior, of a simple closed polygon in the plane
• Computing a minimum-width cubic and hypercubic shell
• The geodesic diameter of polygonal domains
• Maximal distortion of geodesic diameters in polygonal domains
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Title not available (Why is that?)
• 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)