"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.

• Godfried T. Toussaint, "Some open problems on proximity graphs, " First Workshop on Proximity Graphs, Las Cruces, New Mexico, 1989.
(3) You can read my original paper and a more recent survey on the Relative Neighborhood Graph:
• Godfried T. Toussaint, "The relative neighbourhood graph of a finite planar set," Pattern Recognition, Vol. 12, 1980, pp. 261-268. Winner of an Outstanding Paper Award given by the Pattern Recognition Society.
• Godfried T. Toussaint, "Relative neighborhood graphs and their relatives," Proc. IEEE, vol. 80, No. 9, September, 1992, pp. 1502-1517. (with J. Jaromczyk)
(4) Application of proximity graphs to archaeology (Tenochtitlan, Mexico)