Computing the geodesic centers of a polygonal domain

DOI10.1016/J.COMGEO.2015.10.009zbMATH Open1506.68172OpenAlexW2963019203MaRDI QIDQ1622342FDOQ1622342

Authors Sang Won Bae, Matias Korman, Yoshio Okamoto

Publication date 19 November 2018

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

exact algorithmshortest pathpolygonal domaingeodesic center

Mathematics Subject Classification ID

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

Abstract: We present an algorithm that computes the geodesic center of a given polygonal domain. The running time of our algorithm is $O(n^{12+epsilon})$ for any $epsilon>0$, where $n$ is the number of corners of the input polygonal domain. Prior to our work, only the very special case where a simple polygon is given as input has been intensively studied in the 1980s, and an $O(nlogn)$-time algorithm is known by Pollack et al. Our algorithm is the first one that can handle general polygonal domains having one or more polygonal holes.

Recommendations

• scientific article; zbMATH DE number 7030514
• On the geodesic centers of polygonal domains
• scientific article; zbMATH DE number 4051002
• Computing the geodesic center of a simple polygon
• scientific article; zbMATH DE number 6789192

Cites work

• scientific article; zbMATH DE number 1305410 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• scientific article; zbMATH DE number 6789192 (Why is no real title available?)
• Almost tight upper bounds for lower envelopes in higher dimensions
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Computing geodesic furthest neighbors in simple polygons
• Computing the geodesic center of a simple polygon
• Matrix Searching with the Shortest-Path Metric
• New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• The geodesic diameter of polygonal domains

Cited in

(17)

• 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
• On the geodesic centers of polygonal domains
• scientific article; zbMATH DE number 4051002 (Why is no real title available?)
• A linear-time algorithm for the geodesic center of a simple polygon
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• scientific article; zbMATH DE number 6789192 (Why is no real title available?)
• The geodesic diameter of polygonal domains
• The geodesic diameter of polygonal domains
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• scientific article; zbMATH DE number 7030514 (Why is no real title available?)
• scientific article; zbMATH DE number 140467 (Why is no real title available?)
• Computing bisectors in a dynamic geometry environment
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Centroaffine duality for spatial polygons

This page was built for publication: Computing the geodesic centers of a polygonal domain

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