bls@texhrc.UUCP (Brian L. Sumner) (08/29/89)
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!blsboubez@caip.rutgers.edu (Toufic Boubez) (08/30/89)
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