Voronoi diagrams in n · 2o(√lg lg n) time

ABSTRACT

We reexamine fundamental problems from computational geometry in theallword 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(√ 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).

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
• 3: Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Journal of Computer and System Sciences, v.57 n.1, p.74-93, Aug. 1998 [doi>10.1006/jcss.1998.1580]
• 4: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002 [doi>10.1006/jcss.2002.1822]
• 5: Andrej Brodnik , Peter Bro Miltersen , J. Ian Munro, Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.426-439, August 06-08, 1997
• 6: Timothy M. Chan, Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.333-344, October 21-24, 2006 [doi>10.1109/FOCS.2006.62]
• 7: B. Chazelle, H. Edelsbrunner, L.J. Guibas, and M. Sharir. Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica, 11:116--132, 1994.
• 8: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: Yijie Han, Improved fast interger sorting in linear space, Information and Computation, v.170 n.1, p.81-94, October 10, 2001 [doi>10.1006/inco.2001.3053]
• 11: Yijie Han, Deterministic sorting in O(nlog log n) time and linear space, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509993]
• 12: Yijie Han , Mikkel Thorup, Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.135-144, November 16-19, 2002
• 13: D.G. Kirkpatrick and SReisch. Upper bounds for sorting integers on random access machines. Theoret. Comput. Sci., 28:263--276, 1984.
• 14: K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
• 15: Joseph O'Rourke, Computational Geometry in C, Cambridge University Press, New York, NY, 1998
• 16: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 17: Mihai Patrascu, Planar Point Location in Sublogarithmic Time, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.325-332, October 21-24, 2006 [doi>10.1109/FOCS.2006.61]
• 18: Jack Snoeyink, Point location, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 19: M. Thorup. Randomized sorting in O(n log log n) time and linear space using alladdition, shift, and bit-wise boolean operations. J. Algorithms, 42:205--230, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
computational geometry, convex hulls, point location, segment intersection, sorting, word-RAM algorithms