
Flipping Edged in Triangulations 


GLOSSARYConvex Angle: An internal angle which is less than 180 degrees. Convex Hull: The convex hull of a set of points is the smallest convex set that includes the points. The site Convex Hull Algorithms by Tim Lambert gives an excellent tutorial which demonstrates algorithms for computing the convex hull in 3 dimensions.
Convex Quadrilateral: a quadrilateral whose angles are all less than 180 degrees. We have a convex quadrilateral on the left and a nonconvex quadrilateral on the right. Degree of a Vertex: the degree of a vertex v is the number of edges which have v as an endpoint. Delaunay triangulation: For a set P_{n} of points the plane the unique delaunay triangulation, denoted as DT(P_{n} ), is the triangulation such that no point in P_{n} is inside the the circumcircle of any triangle of DT(P_{n} ). DT(P_{n} ) is the dual of the voronoi diagram of P_{n}. The figure showing delaunay triangulation was taken from mathworld.wolfram.com.
Diameter: the diameter of a polygon is defined as the maximum distance between any two points of the polygon. Dual Graph: Given a planar graph G, its geometric dual G* is constructed by placing a vertex in each region of G (including the exterior region) and if two regions have a edge x in common, joining the corresponding vertices by placing an edge x* crossing only x. Edge Flipping: We define flipping an edge e to mean the operation of removing e from T and replacing it by the other diagonal of the convex quadrilateral containing the adjacent triangles. Euler's theorem: For any convex polyhedron, the number of vertices and faces together is exactly two more than the number of edges. Symbolically VE+F=2, where V denotes the vertices, E denotes the edges, and F denotes the faces. For instance, a tetrahedron has four vertices, four faces, and six edges; 46+4=2. Reflex Angle: An internal angle which is greater than or equal to 180 degrees. Triangulation: A triangulation of P_{n} is a partitioning of CH(P_{n}) into a set of triangles T with disjoint interiors, such that the vertices of each triangle T are points of P_{n}. See figure for delaunay triangulation. Spiral Polygon: A polygon Q_{n} is called a spiral polygon if the vertices of Q_{n} can be labeled v_{1},..., v_{s},v_{s+1},...,v_{n} such that v_{1},...,v_{s }are reflex vertices of Q_{n} and v_{s+1},...,v_{n} are convex vertices of Q_{n}. Voronoi Diagram: The partitioning of a plane with a set of n points P_{n} 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. See figure for delaunay triangulation. 
Last Updated
December 2, 2003 