geometric dual http://mathworld.wolfram.com/GeometricDualGraph.html

pic geometricdualgraph.jpg

from that page:

Given a planar graph G, its geometric dual is constructed by placing a vertex in each region of G (including the exterior region) and, if two regions have an edge x in common, joining the corresponding vertices by an edge crossing only x. The result is always a planar pseudograph. However, an abstract graph with more than one embedding on the sphere can give rise to more than one dual.

Whitney showed that the geometric dual graph and combinatorial dual graph are equivalent (Harary 1994, p. 115), and so may simply be called "the" dual graph.


see also: Combinatorial Dual Graph, Dual Graph



voronoi in Mathematica http://mathworld.wolfram.com/VoronoiDiagram.html




pic voronoidiagramMATHWORLD


from that page:

The partitioning of a plane with n points into n convex polygons such that each polygon contains exactly one point and every point in a given polygon is closer to its central point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. The cells are called Dirichlet regions, Thiessen polytopes, or Voronoi polygons. The Mathematica command DiagramPlot[pts] in the Mathematica add-on package DiscreteMath`ComputationalGeometry` (which can be loaded with the command DiscreteMath Computational Geometry plots the Voronoi diagram of the given list of points.

The Delaunay triangulation and Voronoi diagram in are dual to each other in the graph theoretical sense.


see also: Art Gallery Theorem, Computational Geometry, Delaunay Triangulation, Medial Axis, Triangulation, Voronoi Polygon