Given a simple polygonPonnvertices, give a linear time algorithm that determines whether?x?Psuch that?y?P,xy?P=xy. In other words, the segmentxydoes not intersect the exterior of the polygon. HINT: Suppose that such a pointxexisted inP. Study the geometric properties of such a point and see if you can use any of these properties to design an algorithm to compute such a point?

3. Given a simple polygon P on n vertices, give a linear time algorithm that determines whether Elm E P such that Vy E P, my F] P = my. 111 other words, the segment 33y does not intersect the exterior of the polygon. HEIT: Suppose that such a. point a: existed in P. Stud}r the geometric properties of such a point and see if you can use any of these properties to design an algorithm to compute such a. point