ON RECOGNIZING UNIONS OF 2 CONVEX POLYGONS AND RELATED PROBLEMS

A polygon is said to be U2 if it is the union of two convex polygons, and it is said to be P3 if for any three points in the polygon, at lea st two of them are visible to each other. Furthermore, a polygon is sa id to be KR if all of its reflex vertices are in its kernel. It is kno wn that polygons that are U2 are also P3, and polygons that are P3 are also KR. We investigate the geometric properties of these polygon cla sses, and present an O(n) algorithm for determining if a polygon of n sides is U2, P3, KR, or neither. We also present a simple algorithm fo r finding the kernel of a KR polygon. The problem of determining if a polygon is U2 often arises in biomedical image processing.