We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that n points in 3-d can be stored in a linear-space data structure so that all k points inside a query halfspace can be reported in O(log n + k) time. The data structure can be built in O(n log n) expected time. The previous methods with optimal query time required superlinear (O(n log log n)) space.
We also mention consequences, for example, to higher dimensions and to external-memory data structures. As an aside, we partially answer another open question concerning the crossing number in Matousek's shallow partition theorem in the 3-d case (a tool used in many known halfspace range reporting methods).
We revisit a classic problem in computational geometry: preprocessing a planar n-point set to answer nearest neighbor queries. In SoCG 2004, Bronnimann, Chan, and Chen showed that it is possible to design an efficient data structure that takes no extra space at all other than the input array holding a permutation of the points. The best query time known for such "in-place data structures" is O(log^2 n). In this paper, we break the O(log^2 n) barrier by providing a method that answers nearest neighbor queries in time
O((log n)^{log_{3/2} 2} loglog n) = O(log^{1.71} n).The new method uses divide-and-conquer (based on planar separators) in a way that is quite unlike traditional point location methods, and extends previous 1-d data structuring techniques (specifically the van Emde Boas layout). The method has further applications, for example, in answering extreme point queries for a 3-d point set on the boundary of a convex set of constant complexity.
We reexamine fundamental problems from computational geometry in the word RAM model, where input coordinates are integers that fit in a machine word. We develop a new algorithm for offline point location, a two-dimensional analog of sorting where one needs to order points with respect to segments. This result implies, for example, that the Voronoi diagram of n points in the plane can be constructed in (randomized) time n . 2^{O(\sqrt{lg lg n})}. Similar bounds hold for numerous other geometric problems, such as three-dimensional convex hulls, planar Euclidean minimum spanning trees, line segment intersection, and triangulation of non-simple polygons.
In FOCS'06, we developed a data structure for online point location, which implied a bound of O(n lg n / lg lg n) for Voronoi diagrams and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(n lg n) algorithms. As in the field of integer sorting, the main challenge is to find ways to manipulate information, while avoiding the online problem (in that case, predecessor search).
Given a planar subdivision whose coordinates are integers bounded by U <= 2^w, we present a linear-space data structure that can answer point location queries in O(min{ lg n/lglg n, sqrt{lg U/lglg U} }) time on the unit-cost RAM with word size w. This is the first result to beat the standard Theta(lg n) bound for infinite precision models.
As a consequence, we obtain the first o(n lg n) (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 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).
We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take O(log^3 n) expected amortized time, deletions take O(log^6 n) expected amortized time, and extreme-point queries take O(log^2 n) worst-case time. This is the first method that guarantees polylogarithmic update and query cost for arbitrary sequences of insertions and deletions, and improves the previous O(n^epsilon)-time method by Agarwal and Matousek a decade ago. As a consequence, we obtain similar results for nearest neighbor queries in two dimensions and improved results for numerous fundamental geometric problems (such as levels in three dimensions and dynamic Euclidean minimum spanning trees in the plane).
The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.