Optimal Binary Space Partitions in the Plane

摘要

An optimal BSP for a set S of disjoint line segments in the plane is a BSP for 5 that produces the minimum number of cuts. We study optimal bsps for three classes of BSPs, which differ in the splitting lines that can be used when partitioning a set of fragments in the recursive partitioning process: free bsps can use any splitting line, restricted BSPs can only use splitting lines through pairs of fragment endpoints, and auto-partitions can only use splitting lines containing a fragment. We obtain the two following results: — It is NP-hard to decide whether a given set of segments admits an auto-partition that does not make any cuts. — An optimal restricted BSP makes at most 2 times as many cuts as an optimal free BSP for the same set of segments.