You are in a xy plane with a set of points F. You also have a collection P of N sets { P1,...., Pn} where each of the set consist of points of the form (Px,Py). Each set has a different number of points. The problem is given a value k and a distance D, find points existing in F which are within D distance of any point in Pk. What is the optimal way of solving this?

  • 1
    $\begingroup$ "within D distance of points in Pk" -- within D of any point in Pk, or of all points in Pk? Also, this sounds like a competition question -- please post a link so we can see if it is still live. $\endgroup$ Sep 8, 2019 at 21:23
  • $\begingroup$ Any point in Pk. It's not from any existing competitions, just a problem that came out of a discussion. $\endgroup$ Sep 10, 2019 at 4:28
  • $\begingroup$ Thanks. In an initial preprocessing phase I would do the following for each set Pi: (1) For each point p in Pi, find the closest point in F to p (there are algorithms for finding closest points in a plane efficiently); (2) Sort these |Pi| (point in Pi, minimum distance to a point in F) pairs in increasing order of minimum distance and store them in a list. After this, any query can be answered in O(number of output points) time by scanning the Pk-th sorted list and outputting points until the minimum distance just seen exceeds D. $\endgroup$ Sep 10, 2019 at 22:03


Your Answer

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

Browse other questions tagged or ask your own question.