Proof that the algorithm used in the applet is

equivalent to the one described by M.J. Atallah


The original algorithm reads as follows:

Search for the next vertex of polygon A by scanning polygon B until one of the following two conditions is satisfied:

(i) The edge of B being considered is such that the foot (call it z) of the perpendicular from the vertex of A lies between the two end points of the edge. In this case, use z as the end of the current distance.

(ii) The vertex of B being considered (call it v) is such that the perpendicular to the line joining v and the next vertex of A is a supporting line of B. In this case, use v as the end of the current distance.


What we do in the applet is slightly different. We consider sectors and bands emanating for polygon B, and we test whether the next vertex of A lies within those regions.

A band is defined as an infinite region of the plane bounded by an edge of polygon B and the two parallel lines orthogonal to that edge that go through its two end points. It is obvious that this region is equivalent to the region of the plane for which proposition (i) holds.

A sector is defined as an infinite region of the plane that is between two bands. It is bounded by the two bands that correspond to the two edges of which the vertex of B is an end point. Again, it can be easily proved that this region corresponds to the region defined by proposition (ii).