Split the algorithm and conquer each other
I have a problem that must be solved by division and conquest. There is a set S including N points. If there is a square parallel to the axis, it only contains two points p1 and p2 in S, then we call points p1 and p2 to each other.
Now I need to use Divide and conquer algorithm to calculate the number of points in S.
I've been thinking. I have no paths. I need your help. My English is bad, if you have problems ask me I will add. Thansks.
source to share
The trick is to split in such a way that the individual parts are smaller and can be handled independently. We could split the points into two sets using a quicksort-like hinge. But this is much more complicated than it sounds, because if not done correctly, the sets cannot be reduced in special cases or are not independent.
Adding friends . The sizes of the sets that should be evaluated because they cannot be split are greater than 1 (do nothing), 2 (add a pair) and 3 (add 2 to 3 pairs, verification required).
Finding a turning point . Calculate the x mean and y mean and find the closest point to it p
.
Split... Divide the points into 4 sets a, b, c and d as follows. a, b is bottom left, top right split and c, da top left, bottom right split, only keep the best (take a, b if a.size + b.size <= c.size + d.size). This should ensure that the largest unopened set is of size 3 even in special cases (I'm not 100% sure about this, but the algorithm stays the same if it needs to be larger, just more base cases where friends are added). All sets include a pivot point and other points: set a: x <= px || y <py, set b: x> px || y> = py, set c: x <px || y> = py and set d: x> = px || y <py We should get two sets that are roughly 1/2 to 3/4 of all points and can be handled independently. Thus,with this algorithm, a pair of friends can be discovered more than once.
Example:
* * * * * * * * . * * *
* * * => * p * => * * . , . * * bottom-left top-right partition
* * * * * * * * * . * *
* * . * * . * * . . . .
* * . => * p . => * * . , * * . top-left bottom-right partition
* * * * * * * . . * * *
. . . . . . . . . . . .
* * . => * * . => * . . , . * * bottom-left top-right partition
* * * * p * * * * . * .
etc ... simplified:
a | b top-left bottom-right partition: 1st set: a, b, c, p; 2nd set: b, c, d, p.
- p -
c | d bottom-left top-right partition: 1st set: a, c, d, p; 2nd set: a, b, d, p.
The groups are independent because the points in ad and cb cannot be friends, p will always get in the way. The top left bottom right section separates points a from d, and the bottom left top right section separates points b from c.
source to share
How about the following (not necessarily optimal) algorithm in pseudocode?
List<Pair<Point, Point>> findFriends(List<Point> points)
{
List<Pair<Point, Point>> friends = new List<Pair<Point, Point>>();
if (points.Count > 1)
{
if (points.Count == 2)
{
friends.Add(new Pair<Point, Point>(points[0], points[1]);
}
else
{
int xMedian = getMedianX(points);
int yMedian = getMedianY(points);
List<Point> topLeftPoints = selectPoints(points, 0, xMedian-1, yMedian, yMax);
List<Point> bottomLeftPoints = selectPoints(points, 0, xMedian-1, 0, yMedian-1);
List<Point> topRightPoints = selectPoints(points, xMedian, xMax, yMedian, yMax);
List<Point> bottomRightPoints = selectPoints(points, xMedian, xMax, yMedian, yMax);
friends.Add(findFriends(topLeftPoints));
friends.Add(findFriends(bottomLeftPoints));
friends.Add(findFriends(topRightPoints));
friends.Add(findFriends(bottomRightPoints));
}
}
return friends;
}
source to share