Computational Geometry (Fall 2010)

Project 3

(A) Lower envelope of half rays

Consider n rightward rays in the plane. Describe an algorithm with running time 0(nlog n) for finding the lower envelope of the n rightward rays (shown in red in the example below). Your answer should include an argument about that the number of points/segments on the lower envelope is 0(n).

(B) Minimal points in R³

Consider n points p₁,p₂,...,p_n in R³. A point p_i = (x_i,y_i,z_i) is minimal if no other point p_j = (x_j,y_j,z_j) satisfies simultaniously x_j ≤ x_i, y_j ≤ y_i, and z_j ≤ z_i. Describe an algorithm that finds all minimal points in time 0(nlog^c n), where c is a small constant. In the example below the green points show the minimal points for a point set in R².

(C) Smallest enclosing rectangle

Describe an algorithm that given n points in the plane finds a rectangle of minimal area that contains all points. The rectangle is allowed to have sides that are not axis parallel (but the four corners should of course each be 90°). The running time of the algorithm should be 0(nlog n).

You may use the following fact without proof: In the smallest rectangle, one of the sides must touch two of the input points.

(D) Most Densely Polulated Unit Circle

Describe an algorithm that given n points in the plane finds a circle of radius one containing the most numer of points. The algorithm should ideally have a running time of 0(n²).

Deadline: Wednesday December 22, 2010, 23:59.