A linear-time algorithm for the geodesic center of a simple polygon

DOI10.1007/S00454-016-9796-0MaRDI QIDQ728492zbMATH OpenOpenAlexFDO

Authors Hee-Kap Ahn, Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Matias Korman, Eunjin Oh

Publication date 20 December 2016

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

Full work available at URL https://arxiv.org/abs/1501.00561, https://drops.dagstuhl.de/opus/volltexte/2015/5144/

zbMATH Keywords

facility locationgeodesic distancesimple polygons

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given two points in a simple polygon $P$ of $n$ vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within $P$. The geodesic center of $P$ is the unique point in $P$ that minimizes the largest geodesic distance to all other points of $P$. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an $O(nlogn)$-time algorithm that computes the geodesic center of $P$. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.

Recommendations

• scientific article; zbMATH DE number 6789192
• scientific article; zbMATH DE number 4051002
• Computing the geodesic center of a simple polygon
• The geodesic 2-center problem in a simple polygon
• Computing the geodesic centers of a polygonal domain

Cites work

• scientific article; zbMATH DE number 4051002 (Why is no real title available?)
• scientific article; zbMATH DE number 176583 (Why is no real title available?)
• scientific article; zbMATH DE number 637301 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• An optimal algorithm for the rectilinear link center of a rectilinear polygon
• Approximations and optimal geometric divide-and-conquer
• Computing geodesic furthest neighbors in simple polygons
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• Computing the geodesic center of a simple polygon
• Euclidean shortest paths in the presence of rectilinear barriers
• Fast Algorithms for Finding Nearest Common Ancestors
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Matrix Searching with the Shortest-Path Metric
• On the ball spanned by balls
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The furthest-site geodesic Voronoi diagram
• The geodesic diameter of polygonal domains
• The geodesic diameter of polygonal domains
• Triangulating a simple polygon in linear time

Cited in

(24)

• Computing the geodesic center of a simple polygon
• Geodesic center of a simple polygon using a logarithmic number of extra variables
• Maximal distortion of geodesic diameters in polygonal domains
• The geodesic edge center of a simple polygon
• Rectilinear link diameter and radius in a rectilinear polygonal domain
• scientific article; zbMATH DE number 4051002 (Why is no real title available?)
• Piercing pairwise intersecting geodesic disks
• An \(O(n \log n)\) algorithm for computing a link center in a simple polygon
• Convex hulls in polygonal domains
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Rectilinear link diameter and radius in a rectilinear polygonal domain
• scientific article; zbMATH DE number 6789192 (Why is no real title available?)
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• The polygon burning problem
• scientific article; zbMATH DE number 7559212 (Why is no real title available?)
• An algorithm for finding the Chebyshev center of a convex polyhedron
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Covering convex polygons by two congruent disks
• Covering convex polygons by two congruent disks
• Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
• A simple linear algorithm for computing rectilinear 3-centers
• The geodesic 2-center problem in a simple polygon
• \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
• The geodesic farthest-point Voronoi diagram in a simple polygon

This page was built for publication: A linear-time algorithm for the geodesic center of a simple polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q728492)