1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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