Computer Science – Data Structures and Algorithms
Scientific paper
2010-10-10
Computer Science
Data Structures and Algorithms
Journal version of the paper "Voronoi Diagrams in n 2^O(sqrt{lglg n}) Time" from STOC 2007
Scientific paper
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 convex hull of n points in three dimensions can be constructed in (randomized) time n 2^O(sqrt{lglg n}). Similar bounds hold for numerous other geometric problems, such as planar Voronoi diagrams, planar off-line nearest neighbor search, 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/lglg n) for three-dimensional convex hulls and the other problems. Our current bounds are dramatically better, and a convincing improvement over the classic O(nlg 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).
Chan Timothy M.
Patrascu Mihai
No associations
LandOfFree
Transdichotomous Results in Computational Geometry, II: Offline Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Transdichotomous Results in Computational Geometry, II: Offline Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Transdichotomous Results in Computational Geometry, II: Offline Search will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-88288