The Rectilinear Convex Hull of Line Segments

We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a collection of line segments. Namely, we solve the problem of computing and maintaining the rectilinear convex hull of a set of n line segments, while we simultaneously rotate the coordinate axes by an angle that goes from 0 to 2 π. We describe an algorithm that runs in optimal Θ(nlog n) time and Θ(nα(n) ) space for segments that are non-necessarily disjoint, where α(n) is the inverse of the Ackermann’s function. If instead the line segments form a simple polygonal chain, the algorithm can be adapted so as to improve the time and space complexities to Θ(n). © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.