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

点击翻译按钮获取中文摘要

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.