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

DOI10.1142/S0218195900000103zbMath1074.68625OpenAlexW2120092636MaRDI QIDQ4682194

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

computational geometrylink distancesimple polygonAlgorithm design and analysisshortest segment

Mathematics Subject Classification ID

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

Related Items (1)

Optimally computing a shortest weakly visible line segment inside a simple polygon

Cites Work

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

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