Graphics Reference
In-Depth Information
chosen so that
X
Õ
H
(
p
,
n
i
). We claim that one of the hyperplanes
P
(
p
,
n
i
) must
strictly separate
X
and
q
. If this were not so, then
q
would lie in every one of the
halfplanes
H
(
p
,
n
i
) and hence lie in their intersection. Since this intersection lies in
the halfplane
H
(
p
,
n
), which contains
X
, it would follow that
q
lies in
H
(
p
,
n
), which
is a contradiction. Therefore, without loss of generality suppose that P(
p
,
n
1
) strictly
separates
X
and
q
. This hyperplane must clearly contain n linearly independent
points of {
p
1
,
p
2
,...,
p
s
}.
Definition.
A point
v
is said to be a
vertex
or an
extreme point
of a convex set
C
if
v
does not belong to the interior of any segment whose endpoints lie in
C
.
Finding the vertices of the convex hull of a finite set of points is the convex hull
vertex problem. Theorem 17.5.2 leads to a simple algorithm for finding the vertices
of a convex hull.
17.5.3 Corollary.
Let
p
1
,
p
2
,...,
p
s
be points in
R
n
. Assume that
X
=
p
1
p
2
...
p
s
has
dimension n. Let
Y
=
p
1
p
2
...
p
s-1
. Then
p
s
is a vertex of
X
if and only if either
(1)
Y
is (n - 1)-dimensional, or
(2) there is a subset {
r
1
,
r
2
,...,
r
n
} of linearly independent points of {
p
1
,
p
2
,...,
p
s-1
}
so that the hyperplane
H
= aff({
r
1
,
r
2
,...,
r
n
}) strictly separates
Y
and
p
s
.
Proof.
The corollary easily follows from Theorem 17.5.2 and the fact that if
p
s
is
a vertex of
X
, then
p
s
does not belong to
Y
and can be strictly separated from that
set.
Finally, it is easy to see that the proofs of the theorems above lead to an O(m
n+1
)
algorithm for determining whether the convex hulls of s and t points, respectively,
intersect, where m = s + t. We get an O(s
n+1
) algorithm for deciding if a point is a
vertex of the convex hull of s points.
17.6
Triangulating Polygons
Polygonal sets are very common. The simplest of these are simplices. By triangulat-
ing sets one can sometimes reduce problems to problems on simplices. A good case
in point is algebraic topology where triangulations can be used effectively to define
and compute homology groups. There are also many places in CAD/CAGD where tri-
angulations are useful. This section discusses triangulation algorithms for (planar)
polygons (
without
holes).
If a polygon
P
defined by vertices
p
1
,
p
2
,...,
p
k
is convex, then a simple way to
triangulate it is to use triangles
p
1
p
i
p
i+1
, i = 2,3, . . . ,k. See Figure 17.8. Of course, a
real algorithm would have to be more careful if one wants nondegenerate triangles
because vertices might be collinear.
Now consider the general case, but before we get started, it is important that the
reader understand what we mean by a polygon because that term is often used very
loosely. A polygon (defined carefully in Section 6.3 in [AgoM05]) is a bounded closed
planar set whose boundary is a single closed polygonal curve and as such can be
