Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing (Q1940703)

Given a set of planar regions, each of which represents an estimate about an input point, and the exact coordinates of the points arrive some time later and need to be processed quickly. Under certain assumption, the authors show that one can preprocess the input lines \(L\) such that given any set \(P\) of points, each of which lies on a distinct line of \(L\), the corresponding convex hull can be computed in expected time \(O(n \alpha (n) )\), where \(\alpha (.)\) is the inverse Ackermann function [\textit{J. Basch} et al., J. Algorithms 31, No. 1, 1--28 (1999; Zbl 0928.68034)]. The authors' data structure has quadratic preprocessing time and storage and the convex hull algorithm is based on a batched randomized incremental construction similar to Seidel's tracing technique [\textit{R. Seidel}, Comput. Geom. 1, No. 1, 51--64 (1991; Zbl 0733.68092)].