Transdichotomous results in computational geometry, I: Point location in sublogarithmic time

TM Chan, MP a ˇ traşcu - SIAM Journal on Computing, 2009 - SIAM
TM Chan, MP a ˇ traşcu
SIAM Journal on Computing, 2009SIAM
Given a planar subdivision whose coordinates are integers bounded by U\leq2^w, we
present a linear-space data structure that can answer point-location queries in
O(\min{\lgn/\lg\lgn, \lgU/\lg\lgU\}) time on the unit-cost random access machine (RAM) with
word size w. This is the first result to beat the standard Θ(\lgn) bound for infinite precision
models. As a consequence, we obtain the first o(n\lgn) (randomized) algorithms for many
fundamental problems in computational geometry for arbitrary integer input on the word …
Given a planar subdivision whose coordinates are integers bounded by , we present a linear-space data structure that can answer point-location queries in time on the unit-cost random access machine (RAM) with word size w. This is the first result to beat the standard bound for infinite precision models. As a consequence, we obtain the first (randomized) algorithms for many fundamental problems in computational geometry for arbitrary integer input on the word RAM, including: constructing the convex hull of a three-dimensional (3D) point set, computing the Voronoi diagram or the Euclidean minimum spanning tree of a planar point set, triangulating a polygon with holes, and finding intersections among a set of line segments. Higher-dimensional extensions and applications are also discussed. Though computational geometry with bounded precision input has been investigated for a long time, improvements have been limited largely to problems of an orthogonal flavor. Our results surpass this long-standing limitation, answering, for example, a question of Willard (SODA'92).
Society for Industrial and Applied Mathematics