144 Computing in Geographic Information Systems
basic properties of a Delaunay triangulation. Recall that a triangle ∆abc is
in the Delaunay triangulation, if and only if the circumcircle of this triangle
contains no other point in its interior. (We will make the usual general po-
sition assumption that no 4 points are co-circular.) How to test whether a
point d lies within the interior of the circumcircle of ∆abc? It turns out that
this can be reduced to a computable determinant. The point d lies within the
circumcircle defined by ∆abc if and only if:
ln(a, b, c, d) = det
a
x
a
y
a
x
2
+ a
y
2
1
b
x
b
y
b
x
2
+ b
y
2
1
c
x
c
y
c
x
2
+ c
y
2
1
d
x
d
y
d
x
2
+ d
y
2
1
<0 (7.10)
Assuming that this primitive In(a,b,c,d) is available to us when we add the
next point, p
i
, the major steps used ...