Computing conforming partitions of orthogonal polygons with minimum stabbing number

作者：Durocher Stephane; Mehrabi Saeed^*

来源：Theoretical Computer Science, 2017, 689: 157-168.

DOI：10.1016/j.tcs.2017.05.035

• Orthogonal polygons
• Conforming partitions
• Stabbing number
• Approximation algorithms

Let P be an orthogonal polygon with n vertices. A partition of P into rectangles is called conforming if it results from cutting P along a set of interior-disjoint line segments, each having both endpoints on the boundary of P. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any orthogonal line segment inside P. In this paper, we consider the problem of finding a conforming partition of P with minimum stabbing number. We first give an O(n log n)-time algorithm to solve the problem when P is a histogram. For an arbitrary orthogonal polygon (even with holes), we give an integer programming formulation of the problem and show that a simple rounding results in a 2-approximation algorithm for the problem. Finally, we show that the problem is NP-hard if P is allowed to have holes.

• 出版日期2017-8-15