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 S 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