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.
|Title of host publication||Computing and Combinatorics (16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings)|
|Editors||M.T. Thai, S. Sahni|
|Place of Publication||Berlin|
|Publication status||Published - 2010|
|Name||Lecture Notes in Computer Science|