@inproceedings{27efb32f2fda47608e6dafc996445f18,

title = "Optimal binary space partitions in the plane",

abstract = "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.",

author = "{Berg, de}, M.T. and A. Khosravi",

year = "2010",

doi = "10.1007/978-3-642-14031-0_25",

language = "English",

isbn = "978-3-642-14030-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "216--225",

editor = "M.T. Thai and S. Sahni",

booktitle = "Computing and Combinatorics (16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings)",

address = "Germany",

}