@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",
}