# Dror Atariah:

## Observations and analysis in Configuration Spaces

### Kurzbeschreibung

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.