Description

1. Given n points on 2D-plane, propose an algorithm to construct a simple polygon P with all the given points as vertices, and only those. Provide its proof of correctness and deduce its time complexity. (A simple polygon is one in which no two edges intersect each other excepting possibly at their endpoints.
2. (a) A convex polygon P is given as counter-clockwise ordered sequence of n vertices, in general positions, whose locations are supplied as (x, y) co-ordinates on the x-y plane. Given a query point q, propose an algorithm to determine in O(log n) time and O(n) space, including pre-processing, if any, whether or not P includes q.
(b) Write a code to implement your algorithm. Construct a convex polygon with 30 vertices, and show your results for a few internal and external points.
10%