Monotone Partitions of Simple Polygons
摘要
Given a simple polygon P with n vertices in the plane, we consider the problem of partitioning P into subpolygons using horizontal (parallel to the x-axis) line segments drawn inside P. We study three versions of the problem: we require (1) every subpolygon is x-monotone, (2) every subpolygon is y-monotone, and (3) every subpolygon is x- or y-monotone. The objective is to minimize the number of subpolygons in the partition. We give an O(n)-time algorithm for each version. The algorithm for version (1) improves upon the previously best \(O(n \log n)\) -time algorithm. We also show that version (3) is NP-complete if P contains holes.