Polygon triangulation: Efficiency and minimality

DOI10.1016/0196-6774(86)90005-2MaRDI QIDQ3742737zbMATH OpenOpenAlexFDO

Authors T. Asano, Tetsuo Asano, Ron Y. Pinter

Publication date 1986

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(86)90005-2

zbMATH Keywords

holespolynomial time algorithmminimum-number triangulationspartitioning a polygonal region

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Recommendations

• On the minimality of polygon triangulation
• Triangulating Simple Polygons and Equivalent Problems
• Polygon triangulation in \(O(n\log{}\log{}n)\) time with simple data structures
• Linear-size nonobtuse triangulation of polygons
• An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon

Cited in

(12)

• Triangulations (tilings) and certain block triangular matrices
• Graph Drawing
• REGION INTERVISIBILITY IN TERRAINS
• On the minimality of polygon triangulation
• Triangle-Based Heuristics for Area Optimal Polygonizations
• Minimum star partitions of simple polygons in polynomial time
• scientific article; zbMATH DE number 701117 (Why is no real title available?)
• scientific article; zbMATH DE number 1747707 (Why is no real title available?)
• TRIANGULATING DISJOINT JORDAN CHAINS
• Pizza sharing is PPA-hard
• Time-space trade-offs for triangulating a simple polygon
• Draining a polygon-or-rolling a ball out of a polygon

This page was built for publication: Polygon triangulation: Efficiency and minimality

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