Geometry of 3D Environments and Sum of Squares Polynomials
Geometry of 3D Environments and Sum of Squares Polynomials
复制标题
3D 环境的几何形状和多项式平方和
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Vikas Sindhwani
中科院分区：
文献类型：
--
作者：
Amir Ali Ahmadi;G. Hall;A. Makadia;Vikas Sindhwani
受机器人技术和计算机视觉应用的推动，我们使用子级多项式集研究与 3D 环境空间推理相关的问题。这些包括：紧密包含具有凸或近凸基本半代数集的点云（例如，代表障碍物），计算两个这样的集合之间的欧几里得距离，分离两个重叠的凸基本半代数集，以及紧密包含几个基本半代数集与单个凸半代数集的并集。我们使用平方和优化的代数技术，将所有这些任务简化为小尺寸的半定程序，并在现实场景中进行数值实验。
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 distances 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.