Linear-time algorithms for weakly-monotone polygons

DOI10.1016/0925-7721(93)90031-ZMaRDI QIDQ685601zbMATH OpenFDO

Authors Paul J. Heffernan

Publication date 7 August 1994

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(93)90031-Z

zbMATH Keywords

linear-time algorithmssimple polygonstriangulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Triangulating a simple polygon is possible in linear time. But the corresponding algorithm is too complex to be considered practical. Simple optimal algorithms for special classes of polygons are interesting. The author studies a new class of so-called weakly-monotone polygons which contains the monotone class. The place in the hierarchy of simple polygons is discussed and a linear-time detection algorithm for the class is given. The author shows how to triangulate a weakly monotone polygon \(P\) in linear time, without prior knowledge of \(P\)'s weak-monotonicity. The algorithms are practical and conceptually simple.

Recommendations

• A new linear algorithm for triangulating monotone polygons
• Triangulating a simple polygon in linear time
• Recognizing weakly simple polygons
• On geodesic properties of polygons relevant to linear time triangulation
• A new triangulation-linear class of simple polygons

Cites work

• An Optimal Algorithm for Finding the Kernel of a Polygon
• Computational geometry in a curved world
• scientific article; zbMATH DE number 3825165 (Why is no real title available?)
• Monotone Pieces of Chains
• On geodesic properties of polygons relevant to linear time triangulation
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time
• Triangulating Simple Polygons and Equivalent Problems
• Triangulation and shape-complexity

Cited in

(11)

• On geodesic properties of polygons relevant to linear time triangulation
• Triangulating a simple polygon in linear time
• Computing the shortest diagonal of a monotone polygon in linear time
• Recognizing weakly simple polygons
• A linear-time construction of Reuleaux polygons
• A linear time algorithm to remove winding of a simple polygon
• A new linear algorithm for triangulating monotone polygons
• A linear-time algorithm for solving the strong hidden-line problem in a simple polygon
• A new triangulation-linear class of simple polygons
• Detecting weakly simple polygons
• Simplified linear-time Jordan sorting and polygon clipping

This page was built for publication: Linear-time algorithms for weakly-monotone polygons

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