Preprocessing power weighted shortest path data using a s-Well Separated Pair Decomposition
This work addresses computational geometry problems for high-dimensional data analysis, but it appears incremental as it builds on existing algorithms like Dijkstra's without presenting concrete experimental results or performance gains.
The paper tackles the problem of computing s-well separated pairs and K-nearest neighbors in high-dimensional Euclidean space using a power weighted shortest path metric, by developing a fused algorithm that combines these two algorithms. The result is a theoretical description of the algorithms and their dependencies, with several open problems identified for future research.
For $s$ $>$ 0, we consider an algorithm that computes all $s$-well separated pairs in certain point sets in $\mathbb{R}^{n}$, $n$ $>1$. For an integer $K$ $>1$, we also consider an algorithm that is a permutation of Dijkstra's algorithm, that computes $K$-nearest neighbors using a certain power weighted shortest path metric in $\mathbb{R}^{n}$, $n$ $>$ $1$. We describe each algorithm and their respective dependencies on the input data. We introduce a way to combine both algorithms into a fused algorithm. Several open problems are given for future research.