Binary plane partitions for disjoint line segments (Q540437)

A binary space partition for a set of disjoint objects in a Euclidean space is a simple hierarchical decomposition of the space into convex faces. The height of a binary space partition is the height of the tree of recursion. The size of a binary space partition is defined as the number of resulting fragments of the input objects. The main result of this paper is that every set of \(n\) disjoint line segments in the plane admits a binary space partition of size \(O(n\log n / \log \log n)\). The result holds in the case of an auto-partition as well. The author describes an algorithm producing, for \(n\) segments, a binary space partition whose height may be as large as \(\Theta (n)\).