Xref: utzoo sci.math:7747 comp.graphics:7209
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cwjcc!gatech!rutgers!caip.rutgers.edu!boubez
From: boubez@caip.rutgers.edu (Toufic Boubez)
Newsgroups: sci.math,comp.graphics
Subject: Re: References needed
Message-ID: <Aug.29.18.20.09.1989.2719@caip.rutgers.edu>
Date: 29 Aug 89 22:20:10 GMT
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 57

bls@texhrc.UUCP (Brian L. Sumner) writes:

>I'm looking for references on a tesselation of the real plane which has
>been variously attributed to Voronoi, Dirichlet, and Thiessen.
>The idea is that a set of n points, p_i, are given, and the plane is broken
>into a set of polygonal regions, R_i, so that for all x in R_i,
>
>    |x - p | < max |x - p |
>	  i   j!=i       j
>
>i.e. all of the points in R_i are "closest" to R_i.  Once this
>tesselation has been performed, on can construct a very nice triangular
>mesh of the p_i.
>I understand fast ways of computing this tesselation have been found
>and would appreciate any references (or code :-)).  

The original papers:
 o Delaunay, B. "Sur la sphere vide", Bulletin de l'Academie des Sciences de
	l'URSS, 1934.
 o Voronoi, G.M. "Nouvelles applications des parametres continus de la theorie
	des formes quadratiques", Journal fur die Reine und Angewandte Mathematik.
 
More useful stuff :-)

 o Shamos, M.I. "Computational Geometry". Ph.D. Thesis, Yale U., 1978.
 o Green, P.J. and Sibson, R., 'Computing Dirichlet tessellations in the 
plane',
	Computer J., 1977, 20:(2), 168-173.
 o Watson, D.F., 'Computing the n-Dimensional Delaunay tessellation with
	application to Voronoi polytopes', Computer J., 1981, 24:(2), 167-172.

etc...
There are so many...

>Also, if you know
>of any better triangluation algorithms, I would like to hear about them
>too.

Again, Brian, there are so many, and each is better suited for some kind
of problem. It will depend on what kind of domain are you trying to
triangulate. Two suggestions out of many:

 o Watson, D.F. and Philip, G.M. 'Systematic Triangulations', Computer Vision,
	Graph., and Image Proc., 1984, 26, 217-223.
 o Boubez, T.I. et al, 'Mesh Generation for Computational Analysis', Computer
	Aided Eng. J., vol.3, No. 6, October 1986.

It might be a good idea to provide some more info about your particular
problem. Good luck.

>Brian Sumner

toufic

		Toufic Boubez
		boubez@caip.rutgers.edu
		boubez@bass.rutgers.edu