Two of the most ubiquitous concepts in computational geometry are Delaunay triangulation and Voronoi diagrams. The two concepts are closely related, but I find Voronoi diagrams more intuitive.
Consider N emergency teams stationed in an area. If an emergency occurs at location A with coordinates (X,Y), which team should respond to the emergency? All things being equal, the answer is the team closest to A. I must therefore partition the area into “response zones” for the teams. The response zone is the region of points that is closest to a particular emergency station. I end up with a Voronoi diagram. Figure 1 shows an example Voronoi diagram with sites (locations of emergency teams) drawn in gray and the vertices of the Voronoi diagram drawn in black. Voronoi diagrams are planar graphs, if one treats unbounded edges as joining a vertex at infinity.
I also rely on another geometric concept — the medial axis of a shape. Intuitively, the medial axis is an axis of symmetry. (It was introduced by a biologist who studied symmetry in natural shapes.) Figure 2 shows the medial axis of a rectangle. It consists of a horizontal segment and four segments that “shoot” into the corners. If you want to be formal, you can define the medial axis as a locus of circle centers that touch at least two boundary points on the rectangle. Medial axes are closely tied with Voronoi diagrams. Specifically, if you prune the edges of a Voronoi diagram that cross the shape’s boundary, you will get the medial axis. Figure 3 shows the Voronoi diagram for a ¼ shape; the medial axis in Figure 4 is the pruned version.
Figure 5 shows what I call the shape structure graph. It is a meta-graph with respect to the medial axis and retains only the “interesting” vertices. You can learn a lot about a shape by inspecting its shape structure graph.
In the rest of the article, I show how to produce Voronoi diagrams in BGL form, compute the medial axis graph, and compute the shape structure graph.