Computing the L₁ geodesic diameter and center of a simple polygon in linear time

DOI10.1016/J.COMGEO.2015.02.005MaRDI QIDQ2349742zbMATH OpenOpenAlexFDO

Authors Sang Won Bae, Matias Korman, Yoshio Okamoto, Haitao Wang

Publication date 17 June 2015

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

geodesic distancegeodesic diametersimple polygongeodesic center\(L_1\) metricHelly number two

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: In this paper, we show that the $L_1$ geodesic diameter and center of a simple polygon can be computed in linear time. For the purpose, we focus on revealing basic geometric properties of the $L_1$ geodesic balls, that is, the metric balls with respect to the $L_1$ geodesic distance. More specifically, in this paper we show that any family of $L_1$ geodesic balls in any simple polygon has Helly number two, and the $L_1$ geodesic center consists of midpoints of shortest paths between diametral pairs. These properties are crucial for our linear-time algorithms, and do not hold for the Euclidean case.

Recommendations

• Computing the \(L _{1}\) geodesic diameter and center of a simple polygon in linear time
• A linear-time algorithm for the geodesic center of a simple polygon
• scientific article; zbMATH DE number 6789192
• 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 L 1-diameter and center of a simple rectilinear polygon in parallel
• scientific article; zbMATH DE number 4051002
• Computing the geodesic center of a simple polygon

Cites work

• scientific article; zbMATH DE number 176583 (Why is no real title available?)
• A Helly-type theorem for simple polygons
• 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
• Computing geodesic furthest neighbors in simple polygons
• Computing minimum length paths of a given homotopy class
• Computing the \(L _{1}\) geodesic diameter and center of a simple polygon in linear time
• Computing the geodesic center of a simple polygon
• Geometric applications of a matrix-searching algorithm
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Matrix Searching with the Shortest-Path Metric
• Settling the bound on the rectilinear link radius of a simple rectilinear polygon
• The geodesic diameter of polygonal domains
• Two-point \(L_1\) shortest path queries in the plane

Cited in

(13)

• Rectilinear link diameter and radius in a rectilinear polygonal domain
• scientific article; zbMATH DE number 176583 (Why is no real title available?)
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain
• A linear-time algorithm for the geodesic center of a simple polygon
• Rectilinear link diameter and radius in a rectilinear polygonal domain
• Computing the \(L _{1}\) geodesic diameter and center of a simple polygon in linear time
• Shortest paths of mutually visible robots
• Computing the L 1-diameter and center of a simple rectilinear polygon in parallel
• \(L_{1}\) shortest path queries in simple polygons
• \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
• scientific article; zbMATH DE number 6789192 (Why is no real title available?)
• \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
• Computing the \(L_1\) geodesic diameter and center of a polygonal domain

This page was built for publication: Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time

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