Optimal binary space partitions in the plane

M.T. Berg, de, A. Khosravi

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

49 Citaten (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.
Originele taal-2Engels
Pagina's (van-tot)187-205
TijdschriftInternational Journal of Computational Geometry and Applications
Nummer van het tijdschrift3
StatusGepubliceerd - 2012

Vingerafdruk Duik in de onderzoeksthema's van 'Optimal binary space partitions in the plane'. Samen vormen ze een unieke vingerafdruk.

Citeer dit