next up previous

---

Algorithm Counterexample II

The counterexample for the Dobkin and Snyder algorithm that we present here is based on the one described in [1]. It is a convex polygon defined by eight points (p₁, p₂,..., p₈) such that p₃ and p₇ alone achieve the diameter. The other points are arranged to prevent the algorithm from ever encountering p₃ and p₇ as a local maximums of one another (refer to Figures 7 to 12):

1. Points p₁, p₃ and p₅ form an equilateral triangle. We use d to denote the length of the sides of this triangle.
   Figure 7: Equilateral triangle (1 of 6).

   [画像:\begin{figure}\centering \htmlrule\\ \par\begin{center} \epsfbox{figs/dobkin_snyder_1.eps}\ \end{center} \htmlrule \end{figure}]

2. Point x is the intersection point of two lines. The first line passes through p₁ and is perpendicular to segment p₁p₃. The second line passes through p₅ and is perpendicular to segment p₅p₃. Point x is directly below segment p₁p₅; in fact, segment xp₃ is the perpendicular bisector of segment p₁p₅.
   Figure 8: Segments xp₁ and p₁p₃ orthogonal; segments xp₅ and p₁p₅ orthogonal (2 of 6).

   [画像:\begin{figure}\centering \htmlrule\\ \par\begin{center} \epsfbox{figs/dobkin_snyder_2.eps}\ \end{center} \htmlrule \end{figure}]

3. Point p₇ lies inside the triangle xp₁p₅ but outside the circle centered at p₃ with radius d. There is space for p₇ in the triangle because line segments xp₁ and xp₅ are tangents of the circle centered at p₃.
   Figure 9: Point p₇ lies inside triangle xp₁p₅ but d (p₃, p₇) > d (3 of 6).

   [画像:\begin{figure}\centering \htmlrule\\ \par\begin{center} \epsfbox{figs/dobkin_snyder_3.eps}\ \end{center} \htmlrule \end{figure}]

4. Point p₈ lies below the line determined by p₁ and p₇ and inside the circle centered at p₃ with radius d. Similarly, p₆ lies below the line determined by p₅ and p₇ and inside the circle centered at p₃ with radius d. There is space for p₈ because p₇ lies inside triangle xp₁p₅ and segment xp₁ is a tangent of the circle centered at p₃. Symmetric arguments apply to p₆.
   Figure 10: Point p₈ lies below p₁p₇ but d (p₃, p₈) < d; similarly for p₆ (4 of 6).

   [画像:\begin{figure}\centering \htmlrule\\ \par\begin{center} \epsfbox{figs/dobkin_snyder_4.eps}\ \end{center} \htmlrule \end{figure}]

5. Point p₂ lies to the left of the line through p₁ and p₃ and inside the circle centered at p₈ with radius d (p₁, p₈). Similarly, p₄ lies to the right of the line through p₁ and p₅ and inside the circle centered at p₆ with radius d (p₅, p₆). There is space for p₂ because p₈ lies inside triangle xp₁p₅ so the angle p₈p₁p₃ is less than 90 degrees. As a result, the circle centered at p₈ intersects the line determined by p₁ and p₃ at p₁ and somewhere above p₁. Symmetric agruments apply to p₄.
   Figure 11: Point p₂ lies to left of p₁p₃ but d (p₂, p₈) < d (p₁, p₈) (5 of 6).

   [画像:\begin{figure}\centering \htmlrule\\ \par\begin{center} \epsfbox{figs/dobkin_snyder_5.eps}\ \end{center} \htmlrule \end{figure}]

The final polygon is illustrated in Figure 12. Next, we show that the polygon is indeed a counterexample.

See if you can construct the polygon described above and then watch how the Dobkin and Snyder algorithm handles it.

---

next up previous

---

Matthew Suderman
Cmpt 308-507