Finding perfect auto-partitions is NP-hard

M.T. Berg, de, A. Khosravi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

56 Downloads (Pure)


A perfect bsp for a set S of disjoint line segments in the plane is a bsp in which none of the objects is cut. We study a specific class of bsps, called autopartitions and we prove that it is np-hard to find if a perfect auto-partition exists for a set of lines.
Original languageEnglish
Title of host publicationAbstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009)
Publication statusPublished - 2009


Dive into the research topics of 'Finding perfect auto-partitions is NP-hard'. Together they form a unique fingerprint.

Cite this