Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing

Esther Ezra, Wolfgang Mulzer

Motivated by the desire to cope with data imprecision, we study methods for taking advantage of preliminary information about point sets in order to speed up the computation of cer…