Algorithm to find a "balance" point

Question

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

"We say that 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 need to return an index of point which dominates and is dominated by the same amount of points (a 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; }

As this is an example excercise before an algorithm test I guess 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

You could sort the points in lexicographical order. Then a point in the sorted list could only be dominated by points further down in the list. This would at least cut down on the number of comparisons that you're making, but I think it's still O(n^2). — Jeff Irwin
– Jeff Irwin, Commented Dec 1, 2015 at 20:18
is n the amount of coordinates in each point or the amount of points in S? your problem statement seems to suggest the former whereas your code suggests the latter. (your code also suggests that each point only has an x and y coordinate, which differs from point A = (a1, a2, ..., an)) — R Nar
– R Nar, Commented Dec 1, 2015 at 20:25
Can you provide sample input (Points) and expected result for test cases? — smcd
– smcd, Commented Dec 1, 2015 at 21:35

Peter de Rivaz · Accepted Answer · 2015-12-01 20:46:59Z

One idea is to visit the points in order of increasing x coordinate.

As you visit each point you insert its y coordinate in a balanced binary tree (with a complexity of O(logn) per point).

You also query the binary tree to find the number of points with smaller y value, this is the number of points that it dominates.

You can then repeat this process in order of decreasing x coordinate to find the number of points that each point is dominated by.

Overall I believe this gives a O(nlogn) complexity.

Update

As Julian pointed out in the comments, this solution fails if there are multiple points with the same x coordinate. A fix for this is to do all the queries for points with the same x coordinate before adding these points to the binary tree.

It would be huge to see some pseudo- or normal code. So basically let's say im considering i-th point after increasing x sorting. I check in the tree how many lower y are there and this is the amount of points dominated by i-th. What's if I have points (1,2) and (1,3) they don't dominate each oither. Do you have time to post some example code? The nlogn is most likely target complexity though.
That is a very good point, if you have multiple points with the same x value then you should do all the queries before adding the points to the binary tree. Nice catch!
Do you know the complexity of counting the elements in a branch of the binary tree?
You can store the count of elements in each subtree to give a O(logn) approach for counting the elements. When you insert an element in the tree you will also need a O(logn) operation to update these counts.

AlexWien · Accepted Answer · 2015-12-01 20:47:43Z

Task like this are often solved with a class called Plane Sweep Algorithms. It seems that you have to adapt one of the existing Plane Sweep Algorithms.

E.g That one that finds all intersections of all lines. (Line segment intersection).

Read more in Mark De Berg: Computational Geometry, page 20fff

Collectives™ on Stack Overflow

Algorithm to find a "balance" point

2 Answers 2

Update

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Update

4 Comments

Comments

Related