Perfect Binary Space Partitions.
Mark de Berg, Marko de Groot, Mark H. Overmars · 1993
In this paper we discuss some results on perfect binary space partitions on sets of non-intersecting line segments in two dimensions. A binary space partition is a scheme for recursively dividing a configuration of objects by hyperplanes until all objects are separated. A binary space partition is called perfect when none of the objects is cut by the hyperplanes used by the binary space partition. Given a set of n non-intersecting line segments, our method constructs a perfect binary space partition, or decides that no perfect binary space partition exists for the arrangement of line segments, in O(n 2 log n) time.