Let x, y, and z denote the three coordinate axes in the three dimensional space R3 . A point p ∈ R3 is specified by its coordinates along the three axes: p = (x(p), y(p), z(p)). For p, q ∈ R3 , we say

For p; q2R3 , we say that pis dominated byq, if x(p ) x(q ), y(p ) y(q ) and z(p ) z(q ).

Let S= fp 0; p 1; : : : ; p n 1g be a set of npoints in R3 . p i 2 S is called a maximal element of S, if p i is not dominated by any other element of S. The set of all maximal elements of Sis denoted by maxima(S ). The maxima problem is: GivenS, nd maxima (S ).

You will write an e cient program to solve this problem, using the C++ or Java Standard Library functions. One brute-force algorithm to solve this problem is as follows: Compare each point p i 2 S against all the other points in Sto determine if p i is dominated by any of those points; if p i is not dominated by any of them, add it to the output set maxima(S ). This algorithm takes ( n) time for each point p i, for a total of ( n2 ) time.

You will implement an e cient algorithm that is expected to run in ( nlog n) time. The program must be in C++ or Java only. This handout discusses the implementation in C++, using the Standard Template Library (STL). The algorithm consists of three steps.

I. Input: The point set Sis in an input le. The rst line contains the value of n(the number of points). Following that, there will be nlines, each line containing the x, y and zcoordinates of one point. The points must be read and stored in an array P OI N T S[0::(n 1)] of POINT ob jects.

The P OI N T S [i ] ob ject corresponds to point p i, and has four elds: the x, y and z-coordinates (all double ); the boolean eld maximalindicating whether or not the point is maximal.

II. Sorting: Sort the points (i.e., the array P OI N T S) according to their z-coordinates, and reindex them such that z(p 0) z(p 1) : : : z(p n 1).

The sorting must be done using the sortlibrary function: sort(POINTS, POINTS+n) ; this requires that you implement the operator<.

p < q if:z(p ) < z (q ), or z(p ) = z(q ) and y(p ) < y (q ), or z(p ) = z(q ) and y(p ) = y(q ) and x(p ) < x (q ).

III. Finding the Maxima: Process the points, one-by-one, in decreasing order of z-coordinates.

Suppose that, at some instant, you have processed the points p n 1; p n 2; : : : ; p i+1 . You must maintain the 2-dimensional maxima of these points in the ( x; y)-plane; this will be called maxima 2[( i+ 1) ::(n 1)]. It forms a staircase in the ( x; y)-plane.

CONSIDER maintainingmaxima 2[( i+ 1) ::(n 1)] in a Binary Search Tree (BST) keyed on the y-coordinate; each node of BST corresponds to a point in maxima 2[ i + 1 ::n]. As we traverse these nodes in decreasing order of y-coordinate, their x-coordinates increase (thus forming a staircase). Now we want to process p i.

p i has a smaller z-coordinate than the points processed so far (namely, p n 1; p n 2; : : : ; p i+1 ). So, p i 2 maxima (S ) i it is not dominated in the ( x; y)-plane by any of the points in maxima 2[ i + 1 ::n]; i.e., p i is not under the staircase.

The test of whether p i is dominated by any of these points (in the ( x; y)-plane) is performed as follows: Find the point qin BST such that y(q ) is just above (or equal to) y(p i); then p i 2 maxima (S ) i x(p i) > x (q ).

If x(p i) > x (q ), add p i to maxima (S ); also, we need to update the BST so that it represents maxima 2[ i::n ]. The update of the BST is done as follows: First, consider the nodes in the BST whose y-coordinates are less than y(p i), in decreasing order of their y-coordinates; delete them one-by-one, until you come across a point pwith x(p ) > x (p i). Finally, insert p i into the BST.

Each insertion or deletion in a BST takes time (height of the tree). To achieve the ( nlog n) runtime, the above BST must be a height-balanced binary search tree: At any istant, the height of the tree is (log of number nodes in the tree). One example of such a tree is Red-Black Tree (see Chapter 13 in the text book). You will use the STL data structure map.

It is implemented as a Red-Black Tree. In the class, I will explain how to use map.

Variable M axN um has the number of elements in M axima(S ). Print out M axN umand M axima (S ). For each point in M axima(S ), also print out its array index (i.e., the index of the point in P OI N T Sarray).

Your program should be modular, and contain appropriate procedures/functions. No com- ments or other documentation is needed. Use meaningful names for all variables. You will run your program on 10 di erent sets of points; your program should have a loop for this. All the point sets are in the input le infile.txt.

The name of your program le must be maxima.[cpp or java] (corresponding to C++ or Java programs, respectively); the name of your output le must be out le.txt.

ANY ONE INVOLVED IN CHEATING/COPYING (INCLUDING THE ONE WHOSE WORK WAS COPIED) WILL BE SEVERELY PUNISHED.