Topics in Computational Geometry: Curved Objects, Restricted-Orientation Objects, Grasping, and Arrangements

苏万教授将考察直线几何和一般几何的结果，以确定前者中的哪一个可以有效地推广，而后者中的哪一个受益于对k个方向的限制。许多机器人的手由两条平行的边组成，可以靠得更近，也可以离得更远。苏万教授推测，在这个模型中，所有的多边形都承认存在稳定的抓地力。她证明了这一猜想，并为特殊类型的多边形提供了线性时间算法。这项研究的目的是证明猜想的全部一般性，然后研究多面体和曲面物体的相应问题。在二维情况下，可以有效地计算最小二乘回归直线的中位数(LMS)。用拓扑线扫掠替换标准垂直线扫掠会产生更快的算法。目标是发现计算多维最小均方根和动态最小均方根的技术，并确定哪些问题受益于拓扑扫描。

Professor Souvaine will examine results in both rectilinear geometry and general geometry to determine which of the former can be efficiently generalized and which of the latter benefit from a restriction to k orientations. Many robot hands consist of two parallel edges that can move closer together or further apart. Professor Souvaine conjectures that all polygons admit a stable grip in this model. She proved the conjecture and provided linear time algorithms for special classes of polygons. The goal of this research is to prove the conjecture in full generality and then to study the corresponding problems for polyhedra and curved objects. In 2 dimensions, the least median of squares regression line (LMS) can be computed efficiently. Replacing the standard vertical line sweep with a topological line sweep results in a faster algorithm. The goals are to discover techniques for computing multidimensional LMS and dynamic LMS and to determine which problems benefit from topological sweep.