next
up
previous
What's Wrong with the Algorithms?
The
Snyder and Tang algorithm
fails because it relies on the assumption that if a point
u on the boundary of a convex polygon
is furthest from
v also on the boundary, and vice versa, then they achieve the
diameter.
However, we saw that our
oval-shaped convex polygon
contradicts this assumption.
The more interesting case is the
Dobkin and Snyder algorithm.
Its correctness relies on the following two statements:
- If v is the first
local maximum for u
on the boundary path
u...w...v
of a convex polygon
then none of the points other than v
along that path can be a local maximum for w.
In other words,
after the algorithm has found a local maximum v
for u, it can begin its search for a local maximum for w
starting at v.
(Click for the proof.)
- If v is a local maximum for u then
no other point on the boundary of the polygon
is further from v than u.
Together, these two statements prove that,
for every point
u,
the algorithm finds the point
v that is furthest from
u.
The pair that is furthest apart achieves the diameter.
Unfortunately, as was pointed out in [
1],
the second statement is false because
it is based on the incorrect assumption that convex polygons
are
unimodal.
A polygon is unimodal
iff for every point x on its boundary
a traversal of the entire boundary starting at x
takes us monotonically
further from x and then
monotonically
closer to x until we arrive back at x.
By monotonically further from x, we mean that our distance
from x may
remain the same during portions of our traversal
but it must never decrease;
by monotonically closer, we mean the same
except that the distance must never increase.
For example, in Figure 13,
the left polygon is unimodal with respect to point x
because as we traverse the boundary from x to v
by way of u, our distance from x continually increases.
Then, traversing back to x by way of w our distance
from x continually decreases.
The right polygon is not unimodal with respect to point x
because u and w are further from x than point v between
them.
Figure 13:
Unimodal (left) and not unimodal (right) with respect to
x.
A convex polygon
P = (p1, p2, p3, p4) of four points is sufficient
to show that not all convex polygons are unimodal.
See Figure 14.
Figure 14:
Two Multimodal Convex Polygons
The distance between
p1 and
p2
and between
p1 and
p4 is 1.
The
interior angle at
p1 is greater than 0
and less than 180 degrees.
The length of line segment
p1p3 is slightly less than 1
but long enough to intersect
p2p4.
As a result,
p1 has two
local maxima:
p2 and
p4.
We can generalize this example to show that, in fact,
a point can have
n local maxima in a convex polygon
described by 2
n points.
These polygons were originally described in [
1].
The distance between every point
pi,
i even, and
p1 is 1.
The length of line segment
p1pi,
i odd, is slightly less than 1
but long enought to intersect line segment
pi - 1pi + 1.
Thus, all points
pi,
i even, are local maxima for point
p1.
The resulting convex polygon for ten points is illustrated
in Figure
14.
Earlier,
we mentioned that the Dobkin and Snyder algorithm actually relies on
the assumption that a local maximum is the maximum. In other words,
if v is a local maximum of u then v is the furthest point
from u. In the polygons just exhibited, this is actually true.
However, if we perturb p2n so that the distance between p1 and p2n
becomes slightly larger than 1 then the polygon remains convex
but local maximum p2 is now closer to p1 than local maximum p2n.
next
up
previous
Matthew Suderman
Cmpt 308-507
