Lower bound on Computation of 2d voronoi diagrams

[Mantena V Raju <mra5577@cis.ksu.edu>]

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.

Thanks,
Raju


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request@research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.