Deterministic construction for trapezoidal decomposition There is a nice decomposition called trapezoidal to process point location queries given a set of disjoint generally curvilinear segments. I found the randomized algorithm for building this type of decomposition in Berg's book on computational geometry. Can someone point me out papers which report deterministic algorithms with only a little polynomial overhead which provides the same capabilities of trapezoidal decomposition for point location ?
I finally found recent paper titled "Optimal randomized incremental construction for guaranteed logarithmic planar point location" by several authors, where deterministic times are given for query and the seach structure, but expected time for preprocessing.