Given n points in the plane with integer coordinates bounded by U \leqslant 2^{w}, we show that the Voronoi diagram can be constructed in O(min{n logn/loglogn, n\sqrt {\log U}) expected time by a randomized algorithm on the unit-cost RAM with word size w. Similar results are also obtained for many other fundamental problems in computational geometry, such as constructing the convex hull of a 3-dimensional point set, computing the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments.

These are the first results to beat the \Omega(nlogn) algebraic-decision-tree lower bounds known for these problems. The results are all derived from a new twodimensional version of fusion trees that can answer point location queries in O(min{logn/loglogn, \sqrt {\log U}) time with linear space. Higher-dimensional extensions and applications are also mentioned in the paper.