Stupid HTML failed the first time. :(machiavelli_impNovember 15 2008, 11:20:09 UTC
Wow, Kushiel's Dart meets graph theory. And I thought Anafiel Delauney couldn't get any more interesting. Well, I suppose he could have survived. :) (The events of Dart if Delaunay hadn't died for a while would be a wonderful piece of fanfic. Hint, hint to all ficcers out there.)
I think the triangulation ties in more closely with Anafiel if it is defined in terms of graph theory rather than geometry.
Define a graph G as a collection of vertices (dots) connected by edges (lines without a direction) or arcs (lines with a direction). Forget about arcs for a minute, so a graph is just a mathematical join-the-dots. If two vertices are connected by only one edge then that edge is a bridge. It is also possible to connect a single vertex with itself: draw an edge that starts and finishes at the same vertex and doesn't intersect with any other edges. This is a loop (for obvious reasons if you draw it). Easy so far, right?
A face of the graph is a maximal portion of the plane for which any two points can be connected by a curve C such that no point in C is a vertex nor an edge. So a triangle (or any convex polygon) has two faces: one bounded by the three (or n) vertices and an exterior face which is the rest of the plane. (If this is confusing, draw a bunch of dots on the page and join them so that two lines only intersect at a dot. If you can draw a line between any two points on the page without crossing an edge, you've made a tree. Otherwise you should find that you can have both points in one area or another and join them with a non-crossing line, but not pick one point in the interior face and one in the exterior.)
Now here comes the fun bit. Define the dual G* of a graph G by the following: 1. Place one vertex of G* in each face of G, including the exterior face. 2. If there is a bridge in G, add a loop to the nearest vertex in G*. 3. Each edge in G* connects a pair of vertices (in G*) so that it intersects one edge of G once, but no other edges in G or G*. (Try doing this on paper - it's a bit tricky to describe.)
Here's where Kushiel's Dart comes in: Let P = {p1,p2, ... , pn} be a set of vertices in the plane. Define V(pi), the Voronoi cell for pi, to be the set of points in the plane that are closer to pi than to any other vertex. A Voronoi diagram of the plane is what is left of the plane after all the Voronoi cells are removed. The dual of the Voroni diagram is a Delauney triangulation.
Am I a crackhead for thinking this has any relevance to Carey's choice for naming him thus? I'm not sure if Carey knows about topology, but even if she doesn't it's a wonderful coincidence. I squeed insanely over this post, so here's my reasoning. The Voroni diagram shows things that are close to each other, so the vertices might be like a group of conspirators or events, then the edges might be the causes or something that links the events. A graph usually looks nothing like its dual, so the edges and vertices of the Delauney triangulation are totally different from those of the Voroni diagram. Despite this, there is a method for getting one from the other and vice versa, so my interpretation was that Delauney can piece together huge, complicated webs of apparently totally unrelated information and read what it really means.
I hope that clears things up without frying your brain along the way.
I think the triangulation ties in more closely with Anafiel if it is defined in terms of graph theory rather than geometry.
Define a graph G as a collection of vertices (dots) connected by edges (lines without a direction) or arcs (lines with a direction). Forget about arcs for a minute, so a graph is just a mathematical join-the-dots.
If two vertices are connected by only one edge then that edge is a bridge. It is also possible to connect a single vertex with itself: draw an edge that starts and finishes at the same vertex and doesn't intersect with any other edges. This is a loop (for obvious reasons if you draw it).
Easy so far, right?
A face of the graph is a maximal portion of the plane for which any two points can be connected by a curve C such that no point in C is a vertex nor an edge. So a triangle (or any convex polygon) has two faces: one bounded by the three (or n) vertices and an exterior face which is the rest of the plane. (If this is confusing, draw a bunch of dots on the page and join them so that two lines only intersect at a dot. If you can draw a line between any two points on the page without crossing an edge, you've made a tree. Otherwise you should find that you can have both points in one area or another and join them with a non-crossing line, but not pick one point in the interior face and one in the exterior.)
Now here comes the fun bit. Define the dual G* of a graph G by the following:
1. Place one vertex of G* in each face of G, including the exterior face.
2. If there is a bridge in G, add a loop to the nearest vertex in G*.
3. Each edge in G* connects a pair of vertices (in G*) so that it intersects one edge of G once, but no other edges in G or G*.
(Try doing this on paper - it's a bit tricky to describe.)
Here's where Kushiel's Dart comes in: Let P = {p1,p2, ... , pn} be a set of vertices in the plane. Define V(pi), the Voronoi cell for pi, to
be the set of points in the plane that are closer to pi
than to any other vertex. A Voronoi diagram of the plane is what is left of the plane after all the Voronoi cells are removed. The dual of the Voroni diagram is a Delauney triangulation.
Am I a crackhead for thinking this has any relevance to Carey's choice for naming him thus?
I'm not sure if Carey knows about topology, but even if she doesn't it's a wonderful coincidence. I squeed insanely over this post, so here's my reasoning. The Voroni diagram shows things that are close to each other, so the vertices might be like a group of conspirators or events, then the edges might be the causes or something that links the events. A graph usually looks nothing like its dual, so the edges and vertices of the Delauney triangulation are totally different from those of the Voroni diagram. Despite this, there is a method for getting one from the other and vice versa, so my interpretation was that Delauney can piece together huge, complicated webs of apparently totally unrelated information and read what it really means.
I hope that clears things up without frying your brain along the way.
Reply
Leave a comment