A binary space partition is called perfect if none of the objects is cut by the hyperplanes used by the binary space partition. Given a set $S$ of $n$ non-intersecting line segments in the plane, construct a perfect binary space partition or decide that no perfect binary space partition exists.