An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT

DOI10.1142/S0218195900000103MaRDI QIDQ4682194zbMATH OpenOpenAlexFDO

Authors Lyudmil Aleksandrov, Hristo N. Djidjev, Jörg-Rüdiger Sack

Publication date 10 June 2005

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195900000103

zbMATH Keywords

Algorithm design and analysiscomputational geometrylink distanceshortest segmentsimple polygon

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05)

Recommendations

• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• Computing the link center of a simple polygon
• scientific article; zbMATH DE number 1256695
• An O(n n) algorithm for computing a link center in a simple polygon
• An optimal algorithm for the rectilinear link center of a rectilinear polygon

Cites work

• An Algorithm for Determining Visibility of a Simple Polygon from an Internal Line Segment
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
• Computing the link center of a simple polygon
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• LOGARITHMIC-TIME LINK PATH QUERIES IN A SIMPLE POLYGON
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Optimal parallel algorithms for rectilinear link-distance problems
• Optimal shortest path queries in a simple polygon

Cited in

(6)

• An \(O(n\log n)\) algorithm for computing the link center of a simple polygon
• Optimally computing a shortest weakly visible line segment inside a simple polygon
• On the central path problem
• On the central path problem
• scientific article; zbMATH DE number 177553 (Why is no real title available?)
• Linear time algorithm for optimal feed-link placement

This page was built for publication: An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT

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