Finding a shortest diagonal of a simple polygon in linear time

DOI10.1016/0925-7721(95)00032-1MaRDI QIDQ676568zbMATH OpenOpenAlexFDO

Authors Subhash Suri, John Hershberger

Publication date 6 May 1997

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(95)00032-1

zbMATH Keywords

shortest diagonalvisibility constraint

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Computing the shortest diagonal of a monotone polygon in linear time
• Computing the longest diagonal of a simple polygon
• Algorithms for minimum length partitions of polygons
• Voronoi diagrams with barriers and the shortest diagonal problem
• Slicing an ear using prune-and-search

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Computing the shortest diagonal of a monotone polygon in linear time
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Matrix searching with the shortest path metric
• Optimal time bounds for some proximity problems in the plane
• Triangulating a simple polygon in linear time
• Voronoi diagrams with barriers and the shortest diagonal problem

Cited in

(4)

• Computing the longest diagonal of a simple polygon
• COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME
• EFFICIENT ALGORITHMS FOR SOLVING DIAGONAL VISIBILITY PROBLEMS IN A SIMPLE POLYGON
• Computing the shortest diagonal of a monotone polygon in linear time

This page was built for publication: Finding a shortest diagonal 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 Q676568)