6 edited body
source | link

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.

    Tweeted twitter.com/#!/StackCompSci/status/536047560931438592
5 title
| link

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$
source | link

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
source | link
2 edited body
source | link
1
source | link