Xref: utzoo comp.lang.c:36420 comp.lang.fortran:4827 comp.sources.wanted:15407 sci.math:15325
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!corton!mirsa!mirsa.inria.fr
From: odevil@mirsa.inria.fr (Olivier Devillers,L025,657763)
Newsgroups: comp.lang.c,comp.lang.fortran,comp.sources.wanted,sci.math
Subject: Re: REQUEST: Voronoi regions in N dimensions
Message-ID: <10238@mirsa.inria.fr>
Date: 22 Feb 91 16:15:56 GMT
References: <1991Feb20.180810.4799@agate.berkeley.edu>
Sender: news@mirsa.inria.fr
Followup-To: comp.lang.c
Lines: 66
Nntp-Posting-Host: sargas.inria.fr

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