divide and conquer

[Jack Smith]

Hello,

I am working on the following problem. I need a divide and conquer
algorithm to solve the following problem. Any help is appreciated.

I have a set of coordinates (x,y) and each coordinate has an ID and
load factor. The load factor is a count of all the coordinates that
are northeast of a point (x,y) (i.e. all points (x_i,y_i) such that
x_i>=x and y_i>=y). Does anyone know a divide and conquer algorithm i
can use to compute the load factors for the set of coordinates?

Example:
If the user input the following coordinates, the program needs to
output the listed loadfactors:

ID coordinate load factor
12 (3,3) 1
10 (4,2) 1
13 (5,6) 0
7 (2,1) 3

[Steve]

Jack Smith wrote:

< Jack's homework removed>

Jack, sooner or later you're going to have to try and do some of your
homework on your own. Your questions are all very interesting, but it is
not considered good form to post such questions on usenet, and if you do
insist on posting them then perhaps you should be more upfront and
honest about it.

[Phil...]

And you should show that you have done some work yourself.
"Steve" <st***********@hotmail.com> wrote in message
news:3f***********************@lovejoy.zen.co.uk.. .

Jack Smith wrote:

< Jack's homework removed>

Jack, sooner or later you're going to have to try and do some of your
homework on your own. Your questions are all very interesting, but it is
not considered good form to post such questions on usenet, and if you do
insist on posting them then perhaps you should be more upfront and
honest about it.

[Dmytry Lavrov]

st*******@yahoo.com (Jack Smith) wrote in message news:<20**************************@posting.google. com>...

Hello,

I am working on the following problem. I need a divide and conquer
algorithm to solve the following problem. Any help is appreciated.

I have a set of coordinates (x,y) and each coordinate has an ID and
load factor. The load factor is a count of all the coordinates that
are northeast of a point (x,y) (i.e. all points (x_i,y_i) such that
x_i>=x and y_i>=y). Does anyone know a divide and conquer algorithm i
can use to compute the load factors for the set of coordinates?

Example:
If the user input the following coordinates, the program needs to
output the listed loadfactors:

ID coordinate load factor
12 (3,3) 1
10 (4,2) 1
13 (5,6) 0
7 (2,1) 3

Okay,i will give you some not-direct hints:
please foget(!) about "divide and conquer" and "ID",
and try to find solution yourself.Maybe you will find D&C,maybe not .

It's take 2 or 5 minutes for me to find solution(algo)(heh,for some
money($100...) i will tell you how ;-).

I personally HATE tendency to name things
"find divide and conquer algorithm" instead of
"not slower than o(n*log n)".
Because
1: divide and conquer may work as o(n^m * log n) where m may be >2
("hint" 2 ;-)

2: while not proved that o(n*log n) is a fastest,faster is
"possible"(but here it's proved).
Dmytry Lavrov.

--
solutions:
http://DmytryLavrov.narod.ru

[Dmytry Lavrov]

st*******@yahoo.com (Jack Smith) wrote in message news:<20**************************@posting.google. com>...

Hello,

I am working on the following problem. I need a divide and conquer
algorithm to solve the following problem. Any help is appreciated.

I have a set of coordinates (x,y) and each coordinate has an ID and
load factor. The load factor is a count of all the coordinates that
are northeast of a point (x,y) (i.e. all points (x_i,y_i) such that
x_i>=x and y_i>=y). Does anyone know a divide and conquer algorithm i
can use to compute the load factors for the set of coordinates?

Example:
If the user input the following coordinates, the program needs to
output the listed loadfactors:

ID coordinate load factor
12 (3,3) 1
10 (4,2) 1
13 (5,6) 0
7 (2,1) 3

oops,
after another 2 minutes (of waiting while photoshop loads) i found
another,elegant and simplest possible solution.
free hint:
you should completly foget about D&C,to find this divide and conquer
solution!

solution cost:
200$

my email here:
http://dmytrylavrov.narod.ru