Resumen
Well-separated pair decomposition (WSPD) is a well known geometric decomposition used for encoding distances, introduced in a seminal paper by Paul B. Callahan and S. Rao Kosaraju in 1995. WSPD compresses O(n2)" role="presentation">??(??2)O(n2)
O
(
n
2
)
pairwise distances of n given points from Rd" role="presentation">R??Rd
R
d
in O(n)" role="presentation">??(??)O(n)
O
(
n
)
space for a fixed dimension d. However, the main problem with this remarkable decomposition is the ?hidden? dependence on the dimension d, which in practice does not allow for the computation of a WSPD for any dimension d>2" role="presentation">??>2d>2
d
>
2
or d>3" role="presentation">??>3d>3
d
>
3
at best. In this work, I will show how to compute a WSPD for points in Rd" role="presentation">R??Rd
R
d
and for any dimension d. Instead of computing a WSPD directly in Rd" role="presentation">R??Rd
R
d
, I propose to learn nonlinear mapping and transform the data to a lower-dimensional space Rd′" role="presentation">R??'Rd'
R
d
'
, d′=2" role="presentation">??'=2d'=2
d
'
=
2
or d′=3" role="presentation">??'=3d'=3
d
'
=
3
, since only in such low-dimensional spaces can a WSPD be efficiently computed. Furthermore, I estimate the quality of the computed WSPD in the original Rd" role="presentation">????Rd
R
d
space. My experiments show that for different synthetic and real-world datasets my approach allows that a WSPD of size O(n)" role="presentation">??(??)O(n)
O
(
n
)
can still be computed for points in Rd" role="presentation">R??Rd
R
d
for dimensions d much larger than two or three in practice.