The distance between convex sets with Minkowski sum structure: application to collision detection

Xiangfeng Wang (), Junping Zhang () and Wenxing Zhang ()
Additional contact information
Xiangfeng Wang: East China Normal University
Junping Zhang: University of Electronic Science and Technology of China
Wenxing Zhang: University of Electronic Science and Technology of China

Computational Optimization and Applications, 2020, vol. 77, issue 2, No 6, 465-490

Abstract: Abstract The distance between sets is a long-standing computational geometry problem. In robotics, the distance between convex sets with Minkowski sum structure plays a fundamental role in collision detection. However, it is typically nontrivial to be computed, even if the projection onto each component set admits explicit formula. In this paper, we explore the problem of calculating the distance between convex sets arising from robotics. Upon the recent progress in convex optimization community, the proposed model can be efficiently solved by the recent hot-investigated first-order methods, e.g., alternating direction method of multipliers or primal-dual hybrid gradient method. Preliminary numerical results demonstrate that those first-order methods are fairly efficient in solving distance problems in robotics.

Keywords: Distance; Minkowski sum of sets; Projection; Alternating direction method of multipliers; Primal-dual hybrid gradient method; Collision detection (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-020-00211-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:77:y:2020:i:2:d:10.1007_s10589-020-00211-0

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-020-00211-0

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().