Convex hull of imprecise points in o(n log n) time after preprocessing
Esther E. Ezra, Wolfgang Mulzer · 2011
Motivated by the desire to cope with data imprecision, we study methods for preprocessing a set of line-segments (or just lines) in the plane such that whenever we are given a set of points, each of which lies on a distinct object, we can compute their convex hull more efficiently than in "standard settings" (that is, without preprocessing).