This paper presents algorithms for computing constraints on the position of an object due to the presence of obstacles. This problem arises in applications which require choosing how to arrange or move objects among other objects. The basis of the approach presented here is to characterize the position and orientation of the object of interest as a single point in a Configuration Space, in which each coordinate represents a degree of freedom in the position and/or orientation of the object. The configurations forbidden to this object, due to the presence of obstacles, can then be characterized as regions in the Configuration Space. The paper presents algorithms for computing these Configuration Space obstacles when the objects and obstacles are polygons or polyhedra. An approximation technique for high-dimensional Configuration Space obstacles, based on projections of obstacles slices, is described.

Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.

Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.

We address the problem of fast relabeling of deformable Delaunay tetrahedral meshes using a compact uniform grid, with CPU parallelization through OpenMP. This problem is important in visualizing the simulation of deformable objects and arises in scientific visualization, games, computer vision, and motion picture production. Many existing software tools and APIs have the ability to manipulate 3D virtual objects. Prior mesh-based representations either allow topology changes or are fast. We aim for both. Specifically, we improve the efficiency of the relabeling step in the Delaunay deformable mesh invented by Pons and Boissonnat and improved by Tychonievich and Jones. The relabeling step assigns material types to deformed meshes and accounts for 70% of the computation time of Tychonievich and Jones' algorithm. We have designed a deformable mesh algorithm using a Delaunay triangulation and a compact uniform grid with CPU parallelization to obtain greater speed than other methods that support topology changes. On average, over all our experiments and with various 3D objects, the serial implementation of the relabeling step of our work reports a speedup of 2.145 over the previous fastest method, including one outlier whose speedup was 3.934. When running in parallel on 4 cores, on average the relabeling step of our work achieves a speedup of 3.979, with an outlier at 7.63. The average speedup of our parallel relabeling step over our own serial relabeling step is 1.841.Simulation results show that the resulting mesh supports topology changes.

An alternative technique for shape morphing using a surface generating method using partial differential equations is outlined throughout this work. The boundaryvalue nature that is inherent to this surface generation technique together with its mathematical properties are hereby exploited for creating intermediate shapes between an initial shape and a final one. Four alternative shape morphing techniques are proposed here. The first one is based on the use of a linear combination of the boundary conditions associated with the initial and final surfaces, the second one consists of varying the Fourier mode for which the PDE is solved whilst the third results from a combination of the first two. The fourth of these alternatives is based on the manipulation of the spine of the surfaces, which is computed as a by-product of the solution. Results of morphing sequences between two topologically nonequivalent surfaces are presented. Thus, it is shown that the PDE based approach for morphing is capable of obtaining smooth intermediate surfaces automatically in most of the methodologies presented in this work and the spine has been revealed as a powerful tool for morphing surfaces arising from the method proposed here.

At the core of successful manipulation and computation over large geometric data is the notion of approximation, both structural and computational. The focus of this thesis will be on the combinatorial and algorithmic aspects of approximations of point-set data P in d-dimensional Euclidean space. It starts with a study of geometric data depth where the goal is to compute a point which is the 'combinatorial center' of P. Over the past 50 years several such measures of combinatorial centers have been proposed, and we will re-examine several of them: Tukey depth, Simplicial depth, Oja depth and Ray-Shooting depth. This can be generalized to approximations with a subset, leading to the notion of epsilon-nets. There we will study the problem of approximations with respect to convexity. Along the way, this requires re-visiting and generalizing some basic theorems of convex geometry, such as the Caratheodory's theorem. Finally we will turn to the algorithmic aspects of these problems. We present a polynomial-time approximation scheme for computing hitting-sets for disks in the plane. Of separate interest is the technique, an analysis of local-search via locality graphs. A further application of this technique is then presented in computing independent sets in intersection graphs of rectangles in the plane.