Decremental greedy polygons and polyhedra without sharp angles.
D. Eppstein.
arXiv:2507.04538.
Proc. 37th
Canadian Conference on Computational Geometry, 2025,
pp. 85–91.
For given elements and a quality function of an element in a subset, monotonically non-increasing with respect to removals of other elements, we can find the max-min-quality subset by a decremental greedy algorithm that repeatedly removes low-quality subsets. We apply this method to find the max-min-angle polygon for points in the plane, the max-min-weight cycle in a directed graph, and several generalizations of both problems.