An \(O(n\log n)\) algorithm for computing the link center of a simple polygon

DOI10.1007/BF02293040zbMath0776.68108OpenAlexW1990495796WikidataQ62037508 ScholiaQ62037508MaRDI QIDQ1193703

Andrzej Lingas, Hristo N. Djidjev, Jörg-Rüdiger Sack

Publication date: 27 September 1992

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02293040

zbMATH Keywords

algorithmlink centerlink radiussimple \(n\)-vertex polygon

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (16)

Optimally computing a shortest weakly visible line segment inside a simple polygon ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Minimal link visibility paths inside a simple polygon ⋮ Computing the L 1-diameter and center of a simple rectilinear polygon in parallel ⋮ Optimal parallel algorithms for rectilinear link-distance problems ⋮ Optimal on-line algorithms for walking with minimum number of turns in unknown streets ⋮ 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 ⋮ Diffuse reflection diameter and radius for convex-quadrilateralizable polygons ⋮ \(\beta\)-stars or on extending a drawing of a connected subgraph ⋮ An optimal algorithm for minimum-link rectilinear paths in triangulated rectilinear domains ⋮ Visibility with multiple reflections ⋮ Diffuse reflection radius in a simple polygon ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Computing the geodesic center of a simple polygon
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Computing the link center of a simple polygon
• A linear time algorithm for minimum link paths inside a simple polygon
• Shortest path solves edge-to-edge visibility in a polygon
• A Separator Theorem for Planar Graphs
• An O(n log n) algorithm for computing a link center in a simple polygon
• An optimal algorithm for detecting weak visibility of a polygon

This page was built for publication: An \(O(n\log n)\) algorithm for computing the link center of a simple polygon