![](https://csdnimg.cn/release/download_crawler_static/4490126/bg5.jpg)
Two Algorithms for Constructing a Delaunay Triangulation 223
v~
Fig. 2. Lawson's example showing
a triangulation over four cocircular
points. The Voronoi tessellation is
shown as dashed lines.
A fourth criterion has been studied, that of choosing the minimum length
diagonal. Shamos and Hoey 1~2~ claim that a Delaunay triangulation is a
minimum edge length triangulation. Lawson ~9) and Lloyd ~1~1 prove by
counterexample that this is not the case (Fig. 3).
Lawson a~ gives the following
local optimization procedure
(LOP)
for constructing a triangulation. Let e be an internal edge (in contrast to an
edge on the convex hull) of a triangulation and Q be the quadrilateral formed
by the two triangles having e as their common edge. Consider the circum-
circle of one of the triangles. This circle passes through three vertices of Q.
If the fourth vertex of the quadrilateral is within the circle, replace e by the
other diagonal of Q, otherwise no action is taken. An edge of the triangula-
tion is said to be
locally optimal
if an application of the LOP would not
swap it. Since for any set of vertices, the number of triangles in any triangula-
tion is a constant, a linear ordering over the set of all triangles can be defined
as follows. To each triangle in the triangulation we assign a value, which is
14
!
Fig. 3. Lloyd's counterexample to Shamos
and Hoey's claim that a Delaunay triangulation
is a minimum edge length triangulation. The
Voronoi tessellation (shown as dashed lines)
indicates the use of the longer diagonal for a
Delaunay triangulation.