{"ID":2897992,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.04538","arxiv_id":"2507.04538","title":"Decremental Greedy Polygons and Polyhedra Without Sharp Angles","abstract":"We show that the max-min-angle polygon in a planar point set can be found in time $O(n\\log n)$ and a max-min-solid-angle convex polyhedron in a three-dimensional point set can be found in time $O(n^2)$. We also study the maxmin-angle polygonal curve in 3d, which we show to be $\\mathsf{NP}$-hard to find if repetitions are forbidden but can be found in near-cubic time if repeated vertices or line segments are allowed, by reducing the problem to finding a bottleneck cycle in a graph. We formalize a class of problems on which a decremental greedy algorithm can be guaranteed to find an optimal solution, generalizing our max-min-angle and bottleneck cycle algorithms, together with a known algorithm for graph degeneracy.","short_abstract":"We show that the max-min-angle polygon in a planar point set can be found in time $O(n\\log n)$ and a max-min-solid-angle convex polyhedron in a three-dimensional point set can be found in time $O(n^2)$. We also study the maxmin-angle polygonal curve in 3d, which we show to be $\\mathsf{NP}$-hard to find if repetitions a...","url_abs":"https://arxiv.org/abs/2507.04538","url_pdf":"https://arxiv.org/pdf/2507.04538v1","authors":"[\"David Eppstein\"]","published":"2025-07-06T21:07:33Z","proceeding":"cs.CG","tasks":"[\"cs.CG\",\"cs.DS\"]","methods":"[]","has_code":false}