Optimal uniformly monotone partitioning of polygons with holes

Polygon partitioning is an important problem in computational geometry with a long history. In this paper we consider the problem of partitioning a polygon with holes into a minimum number of uniformly monotone components allowing arbitrary Steiner points. We call this the MUMC problem. We show that, given a polygon with nn vertices and hh holes and a scan direction, the MUMC problem relative to this direction can be solved in time O(nlogn+hlog3h)O(nlogn+hlog3h). Our algorithm produces a compressed representation of the subdivision of size O(n)O(n), from which it is possible to extract either the entire decomposition or just the boundary of any desired component, in time proportional to the output size. When the scan direction is not given, the problem can be solved in time O(K(nlogn+hlog3h))O(K(nlogn+hlog3h)), where KK is the number of edges in the polygon’s visibility graph. Our approach is quite different from existing algorithms for monotone decomposition. We show that in O(nlogn)O(nlogn) time the problem can be reduced to the problem of computing a maximum flow in a planar network of size O(h)O(h) with multiple sources and multiple sinks. The problem is then solved by applying any standard network flow algorithm to the resulting network. We also present a practical heuristic for reducing the number of Steiner points.

► We show how to subdivide a polygon into a minimum number of uniformly monotone pieces. ► Our subdivision allows inclusion of Steiner points. ► We reduce the problem into one of finding maximum flow in a planar network.