Optimal binary space partitions in the plane

M.T. Berg, de, A. Khosravi

Research output: Contribution to journalArticleAcademicpeer-review

59 Citations (Scopus)
3 Downloads (Pure)


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 di¿er 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 following two 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
Pages (from-to)187-205
JournalInternational Journal of Computational Geometry and Applications
Issue number3
Publication statusPublished - 2012


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

Cite this