6 edited body

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|XL|$$$$|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.

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|XL|$$.

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.

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.

5 title

# Efective algorithm to find Finding nearest of a list of points on euqclidianEuclidian plane to a given reference point and list of candidates

4 Copy-edit and $\LaTeX$

Problem formulation: Given a list L$$L$$ of n$$n$$ points on euclidianin the Euclidian plane and a reference point R$$R$$ also belonging toin that plane, find a closest point P∊L$$P\in L$$ such that, for all ∀X∊L: |PR|≤|XL|$$X\in L$$, $$|PR|\le|XL|$$.

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

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

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

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

Problem formulation: Given a list L of n points on euclidian plane and a reference point R also belonging to that plane, find a closest point P∊L such that ∀X∊L: |PR|≤|XL|.

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 n, but the number of points may be huge - I need an algorithm that runs in 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 2 or more 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 step.

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|XL|$$.

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.

3 changed requirement for complexity of alg to n log n
2 edited body
1