Finding perfect auto-partitions is NP-hard
de Mt Mark Berg, Amirali Khosravi · TU/e Research Portal · 2009
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.