Finding a shortest diagonal of a simple polygon in linear time

DOI10.1016/0925-7721(95)00032-1zbMATH Open0870.68149OpenAlexW2041863277MaRDI QIDQ676568FDOQ676568

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

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

zbMATH Keywords

shortest diagonalvisibility constraint

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Triangulating a simple polygon in linear time
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Voronoi diagrams with barriers and the shortest diagonal problem
• Optimal time bounds for some proximity problems in the plane
• Computing the shortest diagonal of a monotone polygon in linear time
• Matrix searching with the shortest path metric

Cited In (4)

• Computing the shortest diagonal of a monotone polygon in linear time
• EFFICIENT ALGORITHMS FOR SOLVING DIAGONAL VISIBILITY PROBLEMS IN A SIMPLE POLYGON
• Computing the longest diagonal of a simple polygon
• COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC 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)