[comp.sources.wanted] REQUEST: Voronoi regions in N dimensions

rkowen@violet.berkeley.edu (R.K. Owen) (02/21/91)

I'm looking for a program that builds Voronoi tasselations in N dimensions,
N > 2. I already have the program distributed by NETLIB which works in
two dimensions.

Any pointers are appreciated.     thanks

Dario Bressanini           e-mail     rkowen@violet.berkeley.edu
                                      dario%qmc4@csa.lbl.gov

odevil@mirsa.inria.fr (Olivier Devillers,L025,657763) (02/23/91)

From article <1991Feb20.180810.4799@agate.berkeley.edu>, by rkowen@violet.berkeley.edu (R.K. Owen):
> 
> I'm looking for a program that builds Voronoi tasselations in N dimensions,
> N > 2. I already have the program distributed by NETLIB which works in
> two dimensions.

You can use the Green and Sibson algorithm, or the Delaunay tree, its
randomized variation to get a simple semi-dynamic algorithm.

Clarckson and Shor, and Mulmuley provide also randomized algorithms,
but they are static.

For an optimal worst case algorithm in time O(n \ceil{d/a})
you can use the algorithm of Seidel.

@article{gs,
author = "P.J. Green and R. Sibson",
title = "Computing {Dirichlet} Tesselations in the Plane",
journal = cj,
volume = 21,
year = 1978
}

@inproceedings{BT,
author = "J.D. Boissonnat and M. Teillaud",
title = {A Hierarchical Representation of Objects: The {Delaunay} {Tree}},
booktitle = scg2, year = 1986, month = jun
}
@techreport{deltree,
author = "J.D. Boissonnat and M. Teillaud",
title = {On the Randomized Construction of the {Delaunay} Tree},
institution=inria,
number=1140,
year=1989,
month=dec
}
 
@techreport{Seid,
author = "R. Seidel",
title = "A Convex Hull Algorithm Optimal for Point Sites in Even Dimensions",
institution = "Departement of Computer Science, University British Columbia, Vancouver, BC",
number = 14,
year = 1981
}

@article{claII,
author = "K.L. Clarkson and P.W. Shor",
title = "Applications of Random Sampling in Computational Geometry, {II}",
journal = dcg,
year = 1989,
volume = 4,
number = 5
}

@article{mul2,
author = "K. Mulmuley",
title = "On levels in arrangements and {Vorono\"{\i}\"{\i}} diagrams",
journal = dcg,
note = to be published
}


  _               __  __    ___  __               __  __   __ Tel:+33 93657763
 / / /   / | / / /_  /_/    / / /_ | / / /   /   /_  /_/  /_  Telex: 970 050F
/_/ /__ /  |/ / /__ /  \  _/_/ /__ |/ / /__ /__ /__ /  \ __/  Fax:+33 93657765
INRIA - 2004 Route des Lucioles - 06565 VALBONNE CEDEX (France)                                 odevil@alcor.inria.fr