Description

Total points: 30; Credit: 10%
1 (10 points). You are given two sets of points in the plane, P1 and P2, where P1 P2 = n. A partial classifier is a pair of lines l1 and l2, such that all the points of P1 lie on or above l1 and all the points of P2 lie on or below l2. The cost of the partial classifier is the vertical distance between these lines (see the figure below). Give a geometric interpretation of a partial classifier in the dual plane. What is the cost in the dual setting?

2 (10 points). Given a set of n data-points in the 2D-plane and an axis-parallel rectangular box R, the problem is to report all data points included in box R. Show that this problem can be solved using kdtree in O(n + k) time, where k is the number of data points included in the rectangular query-box. Write the recurrence relation and justify the proof.

3 (10 points). In a town, all streets are axis-parallel (i.e., the network resembles a rectangular grid), and two consecutive parallel streets are 0.5 km apart. There are n houses scattered around the town. A pizza company wants to set up delivery stations in different locations. Assume that all houses and delivery stations are located just on grid intersections. The time for delivery in minute from a station s(x, y) to a house h(w, z) is equal to the taxi-cab distance between s and h , i.e., |x − w| + |y − z|, in km. Sketch an algorithm that minimizes the number of pizza-delivery stations so that any order can be honoured in at most 15 minutes. Discuss its complexity.