Lower bound on Computation of 2d voronoi diagrams

[Gill Barequet]

> From compgeom-owner at research.bell-labs.com Sat Jul 14 19:10 IDT 2001
> X-Authentication-Warning: pollux.cis.ksu.edu: mra5577 owned process doing -bs
> Date: Thu, 12 Jul 2001 22:15:11 -0500 (CDT)
> From: Mantena V Raju <mra5577 at cis.ksu.edu>
> To: compgeom-discuss at research.bell-labs.com
> Subject: Lower bound on Computation of 2d voronoi diagrams
> MIME-Version: 1.0
>
> 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


Given a set I of n integer numbers, construct a set S of 2D points in the
following manner: for each number i in I, put the point (i,0) in S.
Now, from VD(S) you can obtain the sorted I in O(n) time: find the minimum
in I in O(n) time, find its counterpart in S and its record in VD(S) in
O(1) time, and follow the neighborhood relations in VD(S), each in O(1)
time for a total of O(n) time. This will give you the sorted I.

Gill

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