Suggest an O(1) time method for recognizing which of the two subpolygons may intersect L. Your method should detect also a trivial case when the line L cannot intersect any of the subpolygons. Hint: Consider the distances between L and three vertices of the polygon: closest to L end-vertex of the diagonal and two neighbors of this vertex on P. The distance between a point (x',y') and line Ax+By+C=0 is proportional to |Ax'+By'+C|.