Perfect binary space partitions

AbstractA binary space partition is a recursive partitioning of a configuration of objects by hyperplanes until all objects are separated. A binary space partition is called perfect if none of the objects is cut by the hyperplanes used by the binary space partition. We present an algorithm that, given a set S of n non-intersecting line segments in the plane, constructs a perfect binary space partition for S, or decides that no perfect binary space partition exists for S, in O(min(n2, n log3 n+m log n)) time, where m is the number of edges in the visibility graph of S. We also prove that deciding whether a set of segments admits a perfect BSP is 3sum-hard