Algorithm Counterexample II

**Points***p*_{1},*p*_{3}and*p*_{5}form an equilateral triangle. We use*d*to denote the length of the sides of this triangle.**Point**Point*x*is the intersection point of two lines. The first line passes through*p*_{1}and is perpendicular to segment*p*_{1}*p*_{3}. The second line passes through*p*_{5}and is perpendicular to segment*p*_{5}*p*_{3}.*x*is directly below segment*p*_{1}*p*_{5}; in fact, segment*xp*_{3}is the perpendicular bisector of segment*p*_{1}*p*_{5}.**Figure 8:**Segments*xp*_{1}and*p*_{1}*p*_{3}orthogonal; segments*xp*_{5}and*p*_{1}*p*_{5}orthogonal (2 of 6).**Point**There is space for*p*_{7}lies inside the triangle*xp*_{1}*p*_{5}but outside the circle centered at*p*_{3}with radius*d*.*p*_{7}in the triangle because line segments*xp*_{1}and*xp*_{5}are tangents of the circle centered at*p*_{3}.**Point**There is space for*p*_{8}lies below the line determined by*p*_{1}and*p*_{7}and inside the circle centered at*p*_{3}with radius*d*. Similarly,*p*_{6}lies below the line determined by*p*_{5}and*p*_{7}and inside the circle centered at*p*_{3}with radius*d*.*p*_{8}because*p*_{7}lies inside triangle*xp*_{1}*p*_{5}and segment*xp*_{1}is a tangent of the circle centered at*p*_{3}. Symmetric arguments apply to*p*_{6}.**Figure 10:**Point*p*_{8}lies below*p*_{1}*p*_{7}but*d*(*p*_{3},*p*_{8}) <*d*; similarly for*p*_{6}(4 of 6).**Point**There is space for*p*_{2}lies to the left of the line through*p*_{1}and*p*_{3}and inside the circle centered at*p*_{8}with radius*d*(*p*_{1},*p*_{8}). Similarly,*p*_{4}lies to the right of the line through*p*_{1}and*p*_{5}and inside the circle centered at*p*_{6}with radius*d*(*p*_{5},*p*_{6}).*p*_{2}because*p*_{8}lies inside triangle*xp*_{1}*p*_{5}so the angle*p*_{8}*p*_{1}*p*_{3}is less than 90 degrees. As a result, the circle centered at*p*_{8}intersects the line determined by*p*_{1}and*p*_{3}at*p*_{1}and somewhere above*p*_{1}. Symmetric agruments apply to*p*_{4}.

- The polygon is convex.
- The distance between
*p*_{5}and*p*_{1},*p*_{2},*p*_{3}and*p*_{8}is greater than the distance between*p*_{6}and*p*_{1},*p*_{2},*p*_{3}and*p*_{8}, respectively. - The distance between
*p*_{1}and*p*_{4},*p*_{5},*p*_{6},*p*_{7}and*p*_{8}is greater than the distance between*p*_{2}and*p*_{4},*p*_{5},*p*_{6},*p*_{7}and*p*_{8}, respectively. - The diameter of the polygon is achieved only by
*p*_{3}and*p*_{7}.

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

Matthew Suderman

Cmpt 308-507