Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
From MaRDI portal
Publication:2349742
DOI10.1016/j.comgeo.2015.02.005zbMath1318.65011arXiv1312.3711OpenAlexW2057578919MaRDI QIDQ2349742
Sang Won Bae, Yoshio Okamoto, Haitao Wang, Matias Korman
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
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)
Related Items (6)
Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ \(L_{1}\) shortest path queries in simple polygons ⋮ A linear-time algorithm for the geodesic center of a simple polygon ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
Cites Work
- Unnamed Item
- The geodesic diameter of polygonal domains
- 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
- An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
- Computing minimum length paths of a given homotopy class
- Computing geodesic furthest neighbors in simple polygons
- A Helly-type theorem for simple polygons
- An optimal algorithm for the rectilinear link center of a rectilinear polygon
- Settling the bound on the rectilinear link radius of a simple rectilinear polygon
- Matrix Searching with the Shortest-Path Metric
- Two-Point L1 Shortest Path Queries in the Plane
- Computing the L 1 Geodesic Diameter and Center of a Simple Polygon in Linear Time
This page was built for publication: Computing the \(L_1\) geodesic diameter and center of a simple polygon in linear time
