Capturing crossings: Convex hulls of segment and plane intersections

We give a simple O(nlogn) algorithm to compute the convex hull of the (possibly Θ(n²)) intersection points in an arrangement of n line segments in the plane. We also show an arrangement of dn hyperplanes in d-dimensions whose arrangement has Θ(nd−1) intersection points on the convex hull.