Isomorphic Triangulation of Simple Polygons Diana Garroway

Isomorphism

Informally, an isomorphism is a map that preserves sets and relations among elements.  [MathWorld]

Spiderweb Connectivity

The spiderweb connectivity is simply a method for connecting a set of vertices.  These vertices each have a weight assigned to them and this weight is interpreted as the distance from the vertex to a centre point in the end connectivity. For example, if we have 9 vertices and they have the weights of <3, 1, 4, 3, 3, 4, 2, 4, 3>, then we will insert extra (Steiner) points such that the minimum path from each of the  vertices to a centre point is given by the weight.  This is best illustrated by the following figure.  If we think of the connectivity in layers, then each at each layer, the Steiner points connect to there neighbouring vertex of that layer.  If there is not a neighbouring vertex of that layer (for example if the neighbour has smaller weight), then the point will simply be connected to its neighbour.  We also connect the path from the vertex to the centre, through the Stiener points.  In the end we get a connection on the vertices that looks similar to a spiderweb.  The spiderweb connectivity can be created for any set of vertices and weights and yields triangles and quadrilaterals.  The quadrilaterals can simply be triangulated.

Figure 1: The spiderweb connectivity for the sequence <3, 1, 4, 3, 3, 4, 2, 4, 3>, starting at the red vertex.

Steiner Point

An extra point added to a vertex set that was not part of the original set.  (Also called Steiner Vertex).