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 that p is dominated by q, if x(p) ≤ x(q), y(p) ≤ y(q) and z(p) ≤ z(q).

Let S = {p0, p1, . . . , pn−1} be a set of n points in R3

. pi ∈ S is called a maximal element

of S, if pi

is not dominated by any other element of S. The set of all maximal elements of S is

denoted by maxima(S). The maxima problem is: Given S, find maxima(S).

You will write an efficient 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 pi ∈ S

against all the other points in S to determine if pi

is dominated by any of those points; if pi

is not dominated by any of them, add it to the output set maxima(S). This algorithm takes

Θ(n) time for each point pi

, for a total of Θ(n

2

) time.

You will implement an efficient algorithm that is expected to run in Θ(n log 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 S is in an input file. The first line contains the value of n (the number

of points). Following that, there will be n lines, each line containing the x, y and z coordinates

of one point.

The points must be read and stored in an array P OINT S[0..(n − 1)] of POINT objects.

The P OINT S[i] object corresponds to point pi

, and has four fields: the x, y and z-coordinates

(all double); the boolean field maximal indicating whether or not the point is maximal.

II. Sorting: Sort the points (i.e., the array P OINT S) according to their z-coordinates, and

reindex them such that z(p0) ≤ z(p1) ≤ . . . ≤ z(pn−1).

The sorting must be done using the sort library 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 pn−1, pn−2, . . . , pi+1. You must

maintain the 2-dimensional maxima of these points in the (x, y)-plane; this will be called

maxima2[(i + 1)..(n − 1)]. It forms a staircase in the (x, y)-plane.

CONSIDER maintaining maxima2[(i+1)..(n−1)] in a Binary Search Tree (BST) keyed on

the y-coordinate; each node of BST corresponds to a point in maxima2[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 pi

. pi has a smaller z-coordinate than the points processed so far

(namely, pn−1, pn−2, . . . , pi+1). So, pi ∈ maxima(S) iff it is not dominated in the (x, y)-plane

by any of the points in maxima2[i + 1..n]; i.e., pi

is not under the staircase.

The test of whether pi

is dominated by any of these points (in the (x, y)-plane) is performed

as follows: Find the point q in BST such that y(q) is just above (or equal to) y(pi); then

pi ∈ maxima(S) iff x(pi) > x(q).

If x(pi) > x(q), add pi to maxima(S); also, we need to update the BST so that it represents

maxima2[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(pi), in decreasing order of their y-coordinates; delete them

one-by-one, until you come across a point p with x(p) > x(pi). Finally, insert pi

into the BST.

Each insertion or deletion in a BST takes time Θ(height of the tree). To achieve the

Θ(n log 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 axNum has the number of elements in M axima(S). Print out M axNum and

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 OINT S array).

Your program should be modular, and contain appropriate procedures/functions. No comments or other documentation is needed. Use meaningful names for all variables.

You will run your program on 10 different sets of points; your program should have a loop

for this. All the point sets are in the input file infile.txt.

The name of your program file must be maxima.[cpp or java] (corresponding to C++ or

Java programs, respectively); the name of your output file must be outfile.txt.