Balance Point Search Algorithm

Question

I have a problem with better complexity than O (n ^ 2) in the following problem:

"We say that the point A = (a1, a2, ..., an) dominates B = (b1, b2, ..., bn) when a1> b1 & a2> b2 & & ... && an > bn. We are given a set of points S and we need to return the index of the point that dominates and where the same number of points dominates (balance point) or -1 if such a point does not exist. "

int findBalancePoint(Point[] S, int n){ int index = 0; int dominates, isDominated; for(int i = 0; i < n; i++){ index = i; swap(S, 0, i); dominates = isDominated = 0; for(int j = 1; j < n; j++){ if( S[0].x > S[j].x && S[0].y > S[j].y ) dominates++; else if( S[0].x < S[j].x && S[0].y < S[j].y ) isDominated++; } if(dominates == isDominated) return index; } return -1; } 

Since this is an example of exercises before testing the algorithm, I think there is a better solution. Thanks in advance for any help.

Update

Tests:

 Input1: (1,2), (2,1), (3,3), (4,4), (5,6) Result: 2 Input2: (1,1), (3,2), (4,5) Result: 1 Input3: (1,4), (2,3), (3,1), (4,2) Result: 0 or 1 ( doesnt matter which one ) Input4: (1,1), (2,2), (3,3), (4,4) Result: -1 Input5: (1,2), (2,1), (3,3), (3,5), (4,4), (5,6), (6,2) Result: 2 or 3 

Answer 1

One idea is to visit points in ascending x-coordinate.

When you visit each point, you insert its y coordinate into a balanced binary tree (with O (logn) complexity for each point).

You also query the binary tree to find the number of points with a lower y value, this is the number of points at which it dominates.

You can then repeat this process in decreasing x-coordinate to find the number of points at which each point dominates.

In general, I believe this gives O (nlogn) complexity.

Update

As Julian noted in the comments, this solution fails if there are multiple points with the same x coordinate. To fix this, make all queries for points with the same x coordinate before adding these points to the binary tree.

Answer 2

A task like this is often accomplished with a class called Planning Algorithms. It seems that you need to adapt one of the existing aircraft sweep algorithms.

For example, one that finds all intersections of all lines. (Intersection of the line segment).

Read more at Mark De Berg: Computational Geometry, p. 20fff