2
$\begingroup$

Input: A set of points P(x,y). There are two versions of it - Px, sorted by x and Py, sorted by y.

Output: The two even halves of Px, sorted by y.

The trick here is that it has to work in linear time, otherwise, it's rather useless. What I've come up with so far is finding the midpoint of Px, let's call it Px[mid] and then iterating over Py, checking if each point's x coordinate is bigger than Px[mid] and then assigning it to the appropriate half.

Example:

Px = [(1,7),(2,3),(3,1),(4,-2)]
Py = [(4,-2),(3,1),(2,3),(1,7)]
Px[midpoint] = (2,3)
Ly = [(2,3),(1,7)]
Ry = [(4,-2),(3,1)]

This works quite well, if you account for points with equal x coordinates and compare said points by y instead (and vice versa), which sorts them in a way that avoids potential surprises. Where it fails is the following case:

Px = [(1,7),(2,-3),(2,-3),(4,-2)]
Py = [(2,-3),(2,-3),(4,-2),(1,7)]
midpoint = 2
P[midpoint] = (2,-3)
Ly = [(2,-3),(2,-3),(1,7)]
Ry = [(4,-2)]

I can't seem to think of a way to exclude non-distinct points from the left half, when they're equal to the midpoint. Again, keep in mind that this has to work in linear time, so I can't just split Px into two halves and search for points which might belong to it for the odd case.

$\endgroup$
2
$\begingroup$

This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points whose $x$ value is $m$ (where $n$ is the total number of points). These form the first half, and the rest of the points form the second half.

$\endgroup$
  • $\begingroup$ Thanks, dude, it seems so simple now. I did have to iterate over the array twice, but it is still linear time, so no problem there. $\endgroup$ – SUBmarinoff Aug 22 '17 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.