Minimum star partitions of simple polygons in polynomial time

DOI10.46298/THEORETICS.26.2MaRDI QIDQ6858211zbMATH OpenFDO

Authors Mikkel Abrahamsen, Joakim Blikstad, André Nusser, H. Zhang

Publication date 13 February 2026

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.26.2

zbMATH Keywords

computational geometrydynamic programmingpolynomial timestar partition

Mathematics Subject Classification ID

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

Cites work

• A combinatorial theorem in plane geometry
• A short proof of Chvatal's Watchman Theorem
• Computing optimal diameter-bounded polygon partitions
• Convex Decomposition of Polyhedra and Robustness
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• Covering polygons is even Harder
• Cutting polygons into small pieces with chords: Laser-based localization
• Decomposing a Polygon into Simpler Components
• Decomposing the boundary of a nonconvex polyhedron
• Decomposition of Polygons into Convex Sets
• Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
• Detecting weakly simple polygons
• Exact and approximation algorithms for computing optimal fat decompositions
• Fast triangulation of the plane with respect to simple polygons
• scientific article; zbMATH DE number 3986641 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3793444 (Why is no real title available?)
• scientific article; zbMATH DE number 589122 (Why is no real title available?)
• scientific article; zbMATH DE number 1424299 (Why is no real title available?)
• On decomposing polygons into uniformly monotone parts
• On fat partitioning, fat covering and the union size of polygons
• On partitioning rectilinear polygons into star-shaped polygons
• ON THE TIME BOUND FOR CONVEX DECOMPOSITION OF SIMPLE POLYGONS
• Polygon triangulation: Efficiency and minimality
• Probability and real trees. Ecole d'Eté de Probabilités de Saint-Flour XXXV -- 2005. Lecture given at the Saint-Flour probability summer school, July 6--23, 2005.
• Recognizing weakly simple polygons
• Some NP-hard polygon decomposition problems
• The Art Gallery Problem is ∃ℝ-complete
• Triangulating a simple polygon
• Triangulating a simple polygon in linear time

This page was built for publication: Minimum star partitions of simple polygons in polynomial time

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