<p>See the following paper. The two problems are equivalent more or less. To see that, assume that the points are on the unit sphere centered at the origin, and observe that if your NN query $q$ is on the sphere, then the far neighbour for the antipodal point $-q$ is the NN to $q$. There might be a full version written somewhere on the web...</p>

<pre><code>http://dblp.org/rec/conf/soda/GoelIV01
</code></pre>

<p>Yep, here is a postscript of the full version:</p>

<p><a href="http://web.stanford.edu/~ashishg/papers/reductions.ps" rel="nofollow">http://web.stanford.edu/~ashishg/papers/reductions.ps</a></p>

<p>(Postscript is a file format used in the 20th century to ensure that future generations would not be able to read the content of the file.)</p>

CC BY-SA 3.0
2015-04-15T10:20:21.833Z
2015-04-15T10:20:21.833Z
Sariel Har-Peled
<p>Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".</p>

<p>This is the dual of the "near neighbour" problem studied by people like Andone and Indyk. I'm wondering if it has a name in the literature. Certainly "far neighbour" doesn't make much sense.</p>

<p>There are a few references on "farthest point queries", however nothing recent and nothing that works in high dimensions.</p>

<p>Are you aware of a name for the described problem in newer literature?</p>

<ds.algorithms><reference-request><cg.comp-geom><hash-function><high-dimensional-geometry>
Far point queries in high dimensions
Thomas Ahle
# Far point queries in high dimensions

(Asked by: username_0 on 2015-04-15)

Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".

This is the dual of the "near neighbour" problem studied by people like Andone and Indyk. I'm wondering if it has a name in the literature. Certainly "far neighbour" doesn't make much sense.

There are a few references on "farthest point queries", however nothing recent and nothing that works in high dimensions.

Are you aware of a name for the described problem in newer literature?

**Tags:** ds.algorithms, reference-request, cg.comp-geom, hash-function, high-dimensional-geometry


---

## 1 answers

### Answer by username_1 on 2015-04-15. Score: 3

See the following paper. The two problems are equivalent more or less. To see that, assume that the points are on the unit sphere centered at the origin, and observe that if your NN query $q$ is on the sphere, then the far neighbour for the antipodal point $-q$ is the NN to $q$. There might be a full version written somewhere on the web...
http://dblp.org/rec/conf/soda/GoelIV01

Yep, here is a postscript of the full version:
http://web.stanford.edu/~ashishg/papers/reductions.ps
(Postscript is a file format used in the 20th century to ensure that future generations would not be able to read the content of the file.)


---

