three coordinate axes

three coordinate axes

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.

How do you place an order?

It takes a few steps to place an order with Us:

  • The first step is to place your order. You will need to provide us with some basic information about your project.
  • Once you have placed your order, you will be taken to our secure payment page.
  • Once we receive your order, we will carefully review it and match you with a writer who has the skills and experience.
  • Stay in contact with the writer and discuss vital details of research.
  • Your completed proposal will be delivered via email within the specified deadline.

You are secure when using our service

It's critical for each client to feel secure. As a result, we at Research Proposal Writing take precautions to secure your data.

Financial security You may securely pay for your purchase using a variety of secure payment methods.
Personal security The personal information of our clients is secure. Nobody else will have access to it.
Academic security We use a specialized program to check every completed paper to ensure that we deliver no-plagiarism samples.
Web security This website is safe from unauthorized breaches. We maintain our privacy management in line with the latest laws and regulations.

You can get help placing your order. If you have any questions about our services, please contact us. Our support staff is accessible 24 hours a day, 7 days a week.

If you're still looking for a way to improve your grades and hire expert writers, we've got you covered. Place an order on our website, and we'll help you with any paperwork you want. We will exceed your expectations.

Order now Get a quote