R (a favorite open source, object oriented interactive statistical package) has what appears to be a suitably fast algorithm, but I've only used it in a problem with 20 some odd points or so.

As the others have mentioned above, the Voronoi tessellation or mosaic is computed using the (dual graph which is the) Delaunay triangulation. The R function 'veronoi.mosaic' in the package 'tripack' calls a FORTRAN routine. If its convenient enough to do it in R then just call the veronoi.mosaic function (details on getting R and getting the tripack package follow). Otherwise, if you'd rather just use the internal FORTRAN subroutine, you can figure out the meaning of the arguments by looking at the veronoi.mosaic function in R (at the point at which the FORTRAN subroutine 'veronoi' is called) and work backwards.

In any case, all of its open source and works like a charm.

getting R:

http://cran.r-project.org/

the tripack package

http://cran.r-project.org/web/packages/tripack/index.html

Enjoy!

Best Regards,
Grant Izmirlian