Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#303192] of Pankaj K. Agarwal

Papers Published

  1. Shaharabani, D; Salzman, O; Agarwal, PK; Halperin, D, Sparsification of Motion-Planning Roadmaps by Edge Contraction (September, 2012) [1209.4463v1]
    (last updated on 2018/10/21)

    We present Roadmap Sparsification by Edge Contraction (RSEC), a simple and effective algorithm for reducing the size of a motion-planning roadmap. The algorithm exhibits minimal effect on the quality of paths that can be extracted from the new roadmap. The primitive operation used by RSEC is edge contraction - the contraction of a roadmap edge to a single vertex and the connection of the new vertex to the neighboring vertices of the contracted edge. For certain scenarios, we compress more than 98% of the edges and vertices at the cost of degradation of average shortest path length by at most 2%.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320