I have some questions regarding two similar problems.
We are given ONE set of points in 2D (the plane), and we want to find the closest pair of points within this set. I know the divide and conquer algorithm, but I have seen various sources make different arguments for the number of points one needs to check (3, 5, or 7). Which is actually correct and most optimal? A brief proof of correction for the most optimal solution will be appreciated.
We are given TWO sets of points A and B in 2D (the plane), and we want to find the closest pair (a,b) such that $$$a \in A$$$ and $$$b \in B$$$. How can we solve this? Is this a variant of the above problem with only ONE set of points, or does it require something else?
bump
pretty sure the latter task is called bichromatic closest pair
Let's say we'll check points that are within the splitting line by D distance an in a range of [-D, D] of the other coordinate. This is a 2D x D rectangle. Let's split it into eight D/2 x D/2 rectangles. The maximum distance between 2 points that belong to the same rectangle is Dsqrt(2) / 2, which is less than D, so there must be at most 1 point in each rectangle, giving us a bound of 8.
I'm sure it's possible to prove a better bound, but I suspect the tight bound to be around 4 and 6.
About 2 I'm also interested in that. You can solve it in O(NlogN) by computing the voronoi diagram I'm pretty sure, but I'm not sure if it's possible to do it in the same way as the classical closest pair algorithm.
Let me preface this by saying that you're gray. You don't need to know this to improve your rating. Just do contests and upsolve one or two problems consistently. Personally, I have a list where I add two problems after every contest, and I have upsolved about half.
But let me try to answer your question regardless.
I Don't know the D&C solution for the first problem, but I do know how to do it using a sliding window.
If the closest pair of points found so far are at distance D, you keep a D-units-wide window as you slide from left to right. Within the window, you keep points sorted in vertical order (using a
std::set). When you add a new point to the window, you have to check it it's less than D units away from a point in the window. (if it is, you update D and shrink the window)You only need to check the points that have a vertical difference of less than D and there can only be at most 6 such points. (to convince yourself of this fact, draw a Dx2D rectangle and try to fit 7 or more points that are MORE than D units away from each other).
For the second, you can use something like K-D tree for "nearest point in a static set" queries in O(log N) average time. I don't know how to solve it with deterministic complexity. Maybe something with Voronoi diagrams?
KD trees aren't O(logN) for nearest point queries in general, that's only for when points are randomly chosen. Wikipedia mentions O(N^(0.5)) for the 2d case, but I'm not sure if that's right or if someone misinterpreted what's written in the referenced work. I tried reading it once and I wasn't able to understand shit, it doesn't seem like a trivial result.
KD trees have $$$O(N)$$$ worst time complexity, and I believe its $$$O(N)$$$ for the average also. VP-trees are arguably $$$O(\log N)$$$ average but then I can't understand shit either
I thought so when I looked into it, but I wasn't sure enough to edit https://en.wikipedia.org/wiki/Nearest_neighbor_search#Space_partitioning.
I've never heard about VP-trees, it looks interesting. The thing that made me interested in the second thing is https://codeforces.me/gym/104172 problem I, that I tried solving by sqrt decomposition and using bichromatic closest pair as a subroutine. Unfortunately, solving it like that requires not the closest pair but for each point in A you must be able to get the min distance to a point in B. I coded it using KD trees actually now that I think about it and ofc it wasn't even close to passing (the intended solution is way smarter, I recommend checking the problem out).
Oops. Not sure where I read that, thanks for the correction.