Single-Cluster Spectral Graph Partitioning for Robotics Applications
Edwin Olson, Matthew R. Walter, Seth J. Teller, John L. Leonard · 2005
We present SCGP, 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 O(N 2 ) time 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 can outperform RANSAC.