Optimization Online


Geometry of 3D Environments and Sum of Squares Polynomials

Amir Ali Ahmadi (a_a_a***at***princeton.edu)
Georgina Hall (gh4***at***princeton.edu)
Ameesh Makadia (makadia***at***google.com)
Vikas Sindhwani (sindhwani***at***google.com)

Abstract: Motivated by applications in robotics and computer vision, we study problems related to spatial reasoning of a 3D environment using sublevel sets of polynomials. These include: tightly containing a cloud of points (e.g., representing an obstacle) with convex or nearly-convex basic semialgebraic sets, computation of Euclidean distance between two such sets, separation of two convex basic semalgebraic sets that overlap, and tight containment of the union of several basic semialgebraic sets with a single convex one. We use algebraic techniques from sum of squares optimization that reduce all these tasks to semidefinite programs of small size and present numerical experiments in realistic scenarios.

Keywords: Sum of squares optimization, semidefinite programming, bounding volumes, penetration and distance measures

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Applications -- Science and Engineering


Download: [PDF]

Entry Submitted: 01/31/2017
Entry Accepted: 02/01/2017
Entry Last Modified: 03/20/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society