Xref: utzoo sci.math:7739 comp.graphics:7171
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.csd.uwm.edu!cs.utexas.edu!uunet!wuarchive!texbell!nuchat!texhrc!bls
From: bls@texhrc.UUCP (Brian L. Sumner)
Newsgroups: sci.math,comp.graphics
Subject: References needed
Keywords: tesselation,triangulation,voronoi,dirichlet,thiessen
Message-ID: <341@texhrc.UUCP>
Date: 28 Aug 89 19:49:44 GMT
Organization: Texaco Houston Res. Cntr Hou, Tx
Lines: 20

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 :-)).  Also, if you know
of any better triangluation algorithms, I would like to hear about them
too.

Brian Sumner
Phone: 713-954-6000
E-mail: ...!convex!texhrc!bls