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.
Finding nearest of a list of points on Euclidian plane to a given reference point
algorithms;computational geometry;euclidean distance