It always works
It
now remains to demonstrate that the polygons generated by RPA are
representative of the class of all polygons – i.e., that any polygon
may be generated via this method. This follows from the following
observations:
Suppose we have an n-gon P. Let the N vertices of the n-gon be partitioned into the concave and convex sets, V and X
respectively where |N|=|V|+|X| . Clearly |X| > 2 . If we can demonstrate that there are always three adjacent
vertices m, n and o in N where mn and no are edges in the polygon in which m and o are mutually visible, then we are
certain that P can be derived from a polygon of |N| - 1 sides, since the two edges E(mn) and E(no) could have been derived
from a single edge E(mo).
If
|V| = 0 then the polygon is convex and any three consecutive nodes are
mutually visible. If |V| = 1 then the three vertices of the single
concavity are necessarily all mutually visible and we are done.
If |V|>1, choose any concave angle. If its three points are mutually visible then its two line segments may be replaced by
one
showing the n-gon is derivable from an n-1 gon by RPA. If they are not,
then the line of site between the two endpoints of the angle must be
interrupted by a part of the n-gon. This part of the n-gon must, in
turn, contain a concavity. Repeat this process obtaining a finite
sequence of nested concavities. That finite sequence terminates with a
last internal concavity which itself, must have no inner blocking
concavities. The three points of a concave angle within that unblocked
concavity must all be
mutually visible, implying that the n-gon could have been derived from an n-1-gon