Computing the geodesic centers of a polygonal domain

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

Authors: Sang Won Bae, Matias Korman, Yoshio Okamoto 

Publication date: 19 November 2018

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

exact algorithmshortest pathpolygonal domaingeodesic center

Mathematics Subject Classification ID

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

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
• Almost tight upper bounds for lower envelopes in higher dimensions
• The geodesic diameter of polygonal domains
• Title not available (Why is that?)
• Matrix Searching with the Shortest-Path Metric
• Computing the geodesic center of a simple polygon
• New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
• Computing geodesic furthest neighbors in simple polygons
• Title not available (Why is that?)

Cited In (15)

• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
• Title not available (Why is that?)
• A linear-time algorithm for the geodesic center of a simple polygon
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Computing bisectors in a dynamic geometry environment
• Centroaffine duality for spatial polygons
• Title not available (Why is that?)
• The geodesic diameter of polygonal domains
• The geodesic diameter of polygonal domains
• Maximal distortion of geodesic diameters in polygonal domains
• Computing the geodesic center of a simple polygon
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain

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)