Voronoi Diagram Portrait of MyselfVoronoi Diagram Portrait of Myself

Geodesic Properties of Polygons

"Geometry is the right foundation of all painting." - Albrecht Durer

Neither of the above pictures is, in a strict sense, a proximity graph, but it is a proximity structure: the Voronoi diagram of a set of generating points. It is the dual of the Delaunay triangulation of the generating points, and the Delaunay triangulation is a bona-fide proximity graph. The above pictures were made with an amazing imaging software package (VoronoImage) designed by Mark Grundland that allows one to play with fractal Voronoi diagrams. They were made by choosing some generating points at random on an original image, sampling the color of the image at the generating points, computing the Voronoi diagram of the generating points, and finally filling-in each Voronoi cell with the color of the generating point. The picture on the right has many more generating points uniformly distributed, and hence the Voronoi polygons are larger.

This page is still under construction. However, in the mean time you can do several things:

(1) For loads of artistic fun play with Mark Grunland's VoronoImage. It can do much more than what was done above.

(2) For more scientific fun and details of what is known about proximity graphs read a survey on the topic that I wrote in 1992 jointly with Jerzy Jaromczyk (see also below). The short paper below also lists some open problems in the area.

(3) You can read my original paper and a more recent survey on the Relative Neighborhood Graph: (4) Application of proximity graphs to archaeology (Tenochtitlan, Mexico)

Research Interests Homepage