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.