Single-Cluster Spectral Graph Partitioning for Robotics Applications

Citations Over TimeTop 15% of 2005 papers

Abstract

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.

Related Papers

• → Special Issue on Cutting Edge of Robotics in Japan 2013(2013)3 cited
• → Introduction to Robotics(2021)6 cited
• → Python robotics(2003)4 cited
• → Robotics Around the World(1999)
• → Universal Robotics Systems: Homebrew Developments in the Field(1983)