E. Olson, M. Walter, S. Teller, and J. Leonard, Single-Cluster Spectral Graph Partitioning for Robotics Applications, In Proceedings of Robotics: Science and Systems (RSS), Cambridge, MA, USA, June 2005. |
||
| Abstract | We present an algorithm for finding a single cluster of well-connected nodes in a graph. The general problem is NP-hard, but our algorithm produces an approximate solution in $\mathcal{O}(n^2)$ by considering the spectral properties of the graph's adjacency matrix. We show how this algorithm can be used to find sets of self-consistent hypotheses while rejecting incorrect hypotheses, a problem that frequently arises in robotics. We present results from a range-only SLAM system, a polynomial time data association algorithm, and a method for parametric line fitting that outperforms RANSAC. | |
| Download | [pdf] |
@inproceedings{olson05,
AUTHOR = {E. Olson, and M. Walter, and S. Teller, and J. Leonard},
TITLE = {Single-Cluster Spectral Graph Partitioning for Robotics Applications},
BOOKTITLE = {Proceedings of Robotics: Science and Systems ({RSS})},
YEAR = {2005},
MONTH = {June},
ADDRESS = {Cambridge, MA, USA}
}
|
|
|
|