1. Let S be a set of n disjoint line segments in the plane, and let p be a point not on any of the line segments of S. We wish to determine all line segments of S that p can see, that is, all line segments of S that contain some point q so that the open segment pq does not intersect any line segment of S. Give an O(nlogn) time algorithm for solving this problem. See the example shown on the right. [5]
2. Let S be a subdivision of complexity n, represented using DCEL data structure, and let P be a set of m query points. Give an O((n + m) log(n + m)) time algorithm that computes for every point in P in which face of S it is contained. [5]
4. Consider an implementation of Hertel-Melhorn (HM) Algorithm for convex-partitioning of a simple polygon P with n vertices. Assume that a triangulation of P is given. Suggest a data structure and the required procedure so that HM-Algorithm can be implemented in O(n)-time. [5]
.
