Computational Geometry (Fall 2008)

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 R3

Consider n points p1,p2,...,pn in R3. A point pi = (xi,yi,zi) is minimal if no other point pj = (xj,yj,zj) satisfies simultaniously xjxi, yjyi, and zjzi. Describe an algorithm that finds all minimal points in time 0(nlogc n), where c is a small constant. In the example below the green points show the minimal points for a point set in R2.

(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(n2).

Deadline: Monday January 12, 2009.

Important note: The project should be done in groups of up to three persons. The evaluation of the report will be part of the final grade.


This page is maintained by Gerth Stølting Brodal <gerth@cs.au.dk>