Parameterizations in the Configuration Space and Approximations of Related Surfaces
Dror Atariah · Universitätsbibliothek der FU Berlin Hochschulschriftenstelle u. Dokumentenserver · 2014
This work covers three topics that can all be linked to the celebrated motion planning problem of planar robots. When considering a planar robot, which is represented by a convex polygon, it is natural to study an associated configuration space, where each point corresponds to a unique placement of the robot in its physical world. Obstacles in the world of the robot are represented as three-dimensional solids in the associated configuration space. The union of these solids is the so-called forbidden space. Each point of the forbidden space corresponds to a placement of the robot such that its interior intersects one or more obstacles. The remainder of the configuration space is the so-called free space. Of course, the boundary between the free and forbidden spaces is of tremendous interest. The first part of the dissertation provides a simple and geometrically motivated parameterization of the surfaces that constitute the mentioned boundary. Using this parameterization, it is easy to produce various visualizations of the boundary. Furthermore, standard computations that utilize the parameterization yield deep understanding of the differential geometry of the boundary. Clearly, these are two achievements that contribute to the general study of the motion planning problem. In particular, it is also shown that the elements of the boundary corresponding to contacts between an edge of the robot and a vertex of an obstacle are non- developable ruled surfaces --- thus having a negative Gaussian curvature. The negatively curved surfaces that emerge as portions of the discussed boundary, motivated a search for an optimal triangulation of simpler negatively curved surfaces. Specifically, hyperbolic paraboloids (also know as saddles) are considered. The second part of the dissertation provides both interpolating and non-interpolating triangulations of general saddle surfaces. The optimality of the yielded triangulation used for the approximation is twofold:(i) it maintains a fixed error bound, and (ii) minimizes the number of triangles needed to cover a given portion of the saddle. Finally, the third part of the dissertation provides a detailed account of a contribution to the 2D Arrangements package of the "Computational Geometry Algorithms Library". This part of the work considers the computation of arrangements of bounded piecewise linear curves (polylines) in the plane. More precisely, the initial package code, as shipped with version 4.3, was considerably improved in two senses. First, the computations of arrangements of polylines using the modified code improves execution time by about 5% (on average). Secondly, the modified code is much more generic and suitable for further generalizations. As a result, the improved code was accepted for integration into the library and is scheduled to be shipped with its next release. Together, the achievements presented in the dissertation can contribute to the ongoing study of the motion planning problem, as well as to numerous more general purposes.