1
$\begingroup$

Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be trimmed down further. I can't come up with a geometry of points where if you are comparing them in order by sorted y value you would need more than 3 comparisons to get the closest distance. A counterexample would be greatly appreciated.

Put more rigorously, here is what I am trying to prove:

  • Say I have points, p1, p2...p5 sorted by y values non-decreasing and their x values satisfy -delta <= x <= delta.
  • All points are either in Set A or Set B.
  • Points in Set A satisfy -delta <= x <= 0 and all of them are >= delta apart in distance.
  • Points in Set B satisfy 0 <= x <= delta and all of them are >= delta apart in distance.
  • Delta is <= to the minimum of these two values:
    1. The smallest distance between points of Set A
    2. The smallest distance between points of Set B

It is impossible to come up with an arrangement of points that satisfy these conditions so that p1 and p5 are the closest two points and the distance between p1 and p5 is less than delta.

$\endgroup$
5
  • $\begingroup$ Have you checked my answer here? $\endgroup$
    – John L.
    Commented Dec 25, 2020 at 4:16
  • $\begingroup$ Yes and I didn't have enough points to comment! I think your example may be flawed. It appears that you set the median at 79. Point S3 is 1078 or sqrt(1162084) from the median. However points S1 and S3 are sqrt(1000093) apart. Because of this, point S3 would not be included in the comparison strip. I saw you were working on a proof, did you ever finish it? $\endgroup$
    – Sam
    Commented Dec 27, 2020 at 17:11
  • $\begingroup$ "It appears that you set the median at 79". By "median", did you mean "the central line"? That is the line $y=0$. You may want to read my answer carefully. I believe I had finished the proof that 4 points is enough. However, it will take way too long to write it up. $\endgroup$
    – John L.
    Commented Dec 27, 2020 at 18:36
  • $\begingroup$ If the central line is at 0 then your closest points, S0 and S4, would both be on the right side of the comparison strip. In the algorithm, we would already have that distance recorded and be searching for something better than it. Do we need more than 3 comparisons to find something better? Your solution answered my original question but I edited the very end of it to clarify the objective. I'm also left wondering what would happen if we picked points strictly less than delta distance from the median. $\endgroup$
    – Sam
    Commented Dec 28, 2020 at 17:41
  • $\begingroup$ *by better I mean shorter $\endgroup$
    – Sam
    Commented Dec 28, 2020 at 17:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.