On the geodesic centers of polygonal domains

DOI10.4230/LIPICS.ESA.2016.77zbMATH Open1397.68210arXiv1607.05824OpenAlexW2962701233MaRDI QIDQ4606352FDOQ4606352

Authors: Haitao Wang 

Publication date: 2 March 2018

Abstract: In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain $mathcalP$ with a total of $n$ vertices. We discover many interesting observations. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of $mathcalP$ that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the combinatorial size of the shortest path map equivalence decomposition of $mathcalP$, which is known to be $O(n^{10})$. One key observation is a $pi$-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in $O(n^{11}logn)$ time. Previously, an algorithm of $O(n^{12+epsilon})$ time was known for this problem, for any $epsilon>0$.

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

Recommendations

• scientific article; zbMATH DE number 7030514
• The geodesic diameter of polygonal domains
• Computing the geodesic centers of a polygonal domain
• scientific article; zbMATH DE number 6789192
• scientific article; zbMATH DE number 4051002

zbMATH Keywords

shortest pathspolygonal domainsgeodesic centers

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (7)

• Title not available (Why is that?)
• Title not available (Why is that?)
• The polygon burning problem
• The geodesic 2-center problem in a simple polygon
• Centroaffine duality for spatial 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: On the geodesic centers of polygonal domains

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