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:

  1. 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.)

  2. 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.
\begin{figure}\centering
\htmlrule\\
\par\begin{center}
 \epsfbox{figs/unimodal.eps}\
\end{center} \htmlrule \end{figure}

A convex polygon P = (p1p2p3p4) of four points is sufficient to show that not all convex polygons are unimodal. See Figure 14.

Figure 14: Two Multimodal Convex Polygons
\begin{figure}\centering
\htmlrule\\
\par\begin{center}
 \epsfbox{figs/multimodal.eps}\
\end{center} \htmlrule \end{figure}

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 2n 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