This thesis is concerned with the study of some tessellations (or subdivisions) of the plane or of the space and their relation to some optimization problems. Several of the results have a combinatorial flavor, whereas others are strongly connected to the geometry underlying the corresponding problems. The work combines theoretical statements with applied implications and related algorithms, making use of linear algebra, convex geometry, graph theory and many other tools from discrete and computational geometry. 

Regular subdivisions are tessellations resulting from the projection of the lower faces of a polyhedron. In the first part of this thesis, we generalize regular subdivisions introducing the class of recursively-regular subdivisions. Informally speaking, a recursively-regular subdivision is a subdivision that can be obtained by splitting some faces of a regular subdivision by other regular subdivisions (and continue recursively). We also define the finest regular coarsening and the regularity tree of a subdivision. We derive several properties of these two objects, which reflect certain structure in the class of non-regular subdivisions. In particular, the finest regular coarsening of a subdivision is the regular subdivision that is (in a sense) most similar to it. We show that the class of recursively-regular subdivisions is a proper superclass of the regular subdivisions and a proper subclass of the visibility-acyclic subdivisions (in the sense of an acyclicity theorem by Edelsbrunner). We also show that there exist point sets whose recursively-regular triangulations are not connected by geometric bistellar flips. 

We then derive several algorithms related to the studied objects, and point out applications of the main results. In particular, we present relations to tensegrity theory, data visualization, and graph embedding problems. Special attention is paid to the problem of covering the space by placing given floodlights at given points, for which we extend results known since 1981 and discuss two variants of the original problem. 

The second part is concerned with the study of optimal partial matchings for pairs of point sets under translations. First, we regard the least-squares cost function. The best approach to this problem so far is to construct (and explore) a particular tessellation of the space of translations. In every tile of the tessellation there is one matching that is optimal for any position of the point sets corresponding to a translation in that tile. We give the first non-trivial bound on the complexity of this tessellation in dimensions two and higher, and study several structural properties that lead to algorithms whose running time is polynomial in the size of the larger set. 

We address then the analogous problem under the bottleneck cost function. This cost function assigns to every matching the largest distance defined by a matched pair of points. An associated tessellation is shown to have polynomial complexity. This result, together with graph-theoretical tools, allows us to obtain efficient algorithms for the computation of the corresponding minimum under translations that are sensitive to the size of the smaller of the two sets. The lexicographic variant of the bottleneck cost is analyzed as well. 

Finally, we explore natural directions for the generalization of the problems of matching under translations to which many of our results extend.