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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Monotone Partitions of Simple Polygons

  • Jaegun Lee,
  • Hyojeong An,
  • Hwi Kim,
  • Hee-Kap Ahn

摘要

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.