Optimal binary space partitions in the plane

M.T. Berg, de, A. Khosravi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

26 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationComputing and Combinatorics (16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings)
EditorsM.T. Thai, S. Sahni
Place of PublicationBerlin
ISBN (Print)978-3-642-14030-3
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Optimal binary space partitions in the plane'. Together they form a unique fingerprint.

Cite this