2
$\begingroup$

Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$.

Aditional constrains: Trivial algorithm will just iterate all candidate points in $L$, compute their distance to $R$ and select the closest. Complexity of that is $O(n)$, but the number of points may be huge – I need an algorithm that runs in time $O(\log n)$.

Any preprocesing (building data structures etc.) can be done with $L$ but it should run in $O(n\log n)$ time.

Problem extensions: In case that there are multiple closest points $P$ with the same distance from $R$ it would be nice if the algorithm identified that and returned all of them.

I will actually need to detect $m$ nearest points ($m$ is much smaller then $n$). I can do that by running algorithm to find single closest point $m$ times, each time excluding previously found points from search. However it would be nice it the algorithm could be extended to find $m$ closest points in one call.

$\endgroup$
5
  • 1
    $\begingroup$ Look into the closest pair problem which essentially uses a pair of sweep lines to solve this in N logN time. Other possible solutions are divide and conquer. You should be able to modify either to keep track of points by distance. $\endgroup$
    – 1110101001
    Nov 22, 2014 at 3:07
  • 2
    $\begingroup$ This is a classical problem in CG, see en.wikipedia.org/wiki/Point_location $\endgroup$
    – A.Schulz
    Nov 22, 2014 at 6:43
  • $\begingroup$ @A.Schulz I see where you are trying to get - I can divide the plane into (mostly) triangular each containing one "candicate point". Candidate point's area will border set of all points to which that candidate is the closest. The problem here is how to build these areas in linear time. Do you know how to do that? $\endgroup$
    – Rasto
    Nov 23, 2014 at 23:14
  • $\begingroup$ @1110101001 See my comment above - I would be able to modify it I am able to build "closest areas" above each point from L in linear time. How that can be done? $\endgroup$
    – Rasto
    Nov 23, 2014 at 23:17
  • $\begingroup$ @Raphael Tried a lot of approaches but for none works for general case. Try to think of some algorithm and then try to break it - you will amost certanly find a L and R for which your algorithm does not work or runs longer then in log time. It is really harder then it seems. Also see my comments above. $\endgroup$
    – Rasto
    Nov 23, 2014 at 23:21

1 Answer 1

1
$\begingroup$

You can build a 2d binary search tree for the points in $L$ and then have closes-point queries done in expected $O(\log n)$ time: (see this presentation by Robert Sedgewick, pp.26-27). However, the worst-case time is still $O(n)$. An example of the worst-case input is the situation when all the points from $L$ lie on a circle and $R$ is the center of that circle.

$\endgroup$

Your Answer

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

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