Computing the shortest diagonal of a monotone polygon in linear time

DOI10.1016/0020-0190(92)90227-MMaRDI QIDQ1198084zbMATH OpenOpenAlexFDO

Authors Binhai Zhu

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90227-m

zbMATH Keywords

monotone polygonshortest diagonal

Mathematics Subject Classification ID

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

Review text

We improve the results of \textit{B. Zhu} and \textit{A. Mirzaian} [A linear time algorithm to find the shortest diagonal of a unimonotone polygon, Tech. Rept. CS-90-8, Dept. of Computer Science, York University (1990)] to present a linear time algorithm for an arbitrary monotone polygon.

Recommendations

• Finding a shortest diagonal of a simple polygon in linear time
• A new linear algorithm for triangulating monotone polygons
• Computing the longest diagonal of a simple polygon
• Linear-time algorithms for weakly-monotone polygons
• Finding the convex hull of a simple polygon in linear time

Cites work

• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• scientific article; zbMATH DE number 140463 (Why is no real title available?)
• Triangulating Simple Polygons and Equivalent Problems

Cited in

(2)

• Finding a shortest diagonal of a simple polygon in linear time
• Computing the longest diagonal of a simple polygon

This page was built for publication: Computing the shortest diagonal of a monotone polygon in linear time

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