Lower bound on Computation of 2d voronoi diagrams
Mantena V Raju
mra5577 at cis.ksu.edu
Thu Jul 12 23:15:11 PDT 2001
The lower bound for computing voronoi diagrams is bigomega(n log n). The
reason cited for this is that
The problem of sorting n real number is reducible to the problem of
computing Voronoi diagrams. This is stated on page 151 of the book
COMPUTATIONAL GEOMETRY AND APPLICATIONS
2nd EDITION by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf
I don't quite figure out how sorting of n real number is reducible to
finding the voronoi diagram of n sites.
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce