Finding perfect auto-partitions is NP-hard

M.T. Berg, de, A. Khosravi

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

41 Downloads (Pure)

Abstract

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)
Pages255-258
Publication statusPublished - 2009

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

  • Cite this

    Berg, de, M. T., & Khosravi, A. (2009). Finding perfect auto-partitions is NP-hard. In Abstracts 25th European Workshop on Computational Geometry (EuroCG'09, Brussels, Belgium, March 16-18, 2009) (pp. 255-258)