Timeline for What is the most general class of metric spaces for which the closest pair of points in a finite subset can be found in time O(n^(1+eps))?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2023 at 15:58 | comment | added | The Amplitwist |
The link to sciencedirect.com is broken, but the article can be found at doi:10.1006/jagm.1997.0873 (Zbl 0888.68061).
|
|
| Sep 5, 2010 at 9:04 | vote | accept | Dan Brumleve | ||
| Aug 19, 2010 at 20:46 | comment | added | Joseph O'Rourke | @François: You are right, I only meant the algorithm still works, but I implied the complexity was the same when it is not. Corrected now. Thanks for catching this! | |
| Aug 19, 2010 at 20:41 | history | edited | Joseph O'Rourke | CC BY-SA 2.5 |
Removed the now superfluous remark about the constant.
|
| Aug 19, 2010 at 13:02 | comment | added | François G. Dorais | @Joseph: The bound given by Bentley on p. 227 is $O(n\log^{d-1}n)$. Did I miss something? | |
| Aug 19, 2010 at 0:55 | comment | added | Bill Johnson | @Piero: $n$ points in any metric space embed isometrically into $\ell_\infty^{n-1}$. If the points are labeled $x_0,\dots, x_{n-1}$, map a point $x$ to $(d(x,x_0),\dots,d(x,x_{n-1}$. You of course cannot embed every finite metric space isometrically into a Hilbert space. | |
| Aug 19, 2010 at 0:25 | comment | added | Piero D'Ancona | Beautiful. One thing I do not understand: essentially, Dan's question is reduced to a different one. Namely, is it possible to find an $\mathbb{R}^d$ such that there are n points at the same mutual distances as the points in the original metric space? and how large is d, and does it depend on n? or am I wrong. | |
| Aug 19, 2010 at 0:14 | comment | added | Dan Brumleve | Thanks, this is a helpful reference. It looks like my suspicion was completely wrong! | |
| Aug 18, 2010 at 23:50 | history | answered | Joseph O'Rourke | CC BY-SA 2.5 |