Description

Q1. Consider the simple polygon shown below:

Show a partition with minimum number of y-monotone polygons. Justify the minimality of partition.
[3 + 2]
2. Given n points in general positions in the 2D-plane, sketch an O(n log n)-time algorithm for determining the Tukey depth of a query point. [5]
3. You are given a simple polygon P with n sides and two points s and t in P, and let T denote a triangulation of P. Show that the Euclidean shortest path (ESP) between s and t is unique. Also show that the minimal set of triangles containing the ESP forms a path in the dual tree of T. [2 + 3]
4.(a) Let L be an arbitrary line segment interior to a convex polygon P with n vertices. Does there exist a triangulation such that the number of intersections of L with all diagonals become O(log n)? If so, provide a method for constructing such a triangulation. [3]

(b) Are there any polygons such that for any triangulation, such a line L will have Ω(n) intersections
with diagonals? If so, show an example. [2]