The study of the interactions between multidimensional boxes (i.e., axis aligned d-dimensional hyperrectangles) has found important applications in distinct areas, including computational geometry, databases, graph theory and networks. We deal with some open questions on this matter, focusing on three main issues: finding matchings of a set of points with boxes, finding redundancies in the region covered by a set of boxes, and computing distinct measures of this region. We consider three corresponding groups of problems, and study their computational complexity, in both the worst-case and adaptive analysis frameworks. We first consider problems on computing distinct measures of the region covered by a set B of boxes. We introduce the computation of the depth distribution of B, which generalizes the computation of its Klee's measure and maximum depth, respectively. We describe distinct algorithms to compute the depth distribution of a set of boxes, and introduce refined computational upper bounds for the Klee's Measure and Maximum Depth problems, respectively, by considering distinct measures of difficulty of the input of these problems. We introduce various conditional lower bounds for the computational complexity of the Depth Distribution problem. These lower bounds not only provide insights on how fast the depth distribution can be computed, but also clarify the relation between the Depth Distribution problem and other fundamental problems in computer science. Then, we consider problems on matching pairs of points in a given finite set with boxes in distinct settings. A matching of a set S of colored points with boxes is a set of axis-aligned closed rectangles, pair-wise disjoint, and such that each box contains exactly two points of S. The problems we consider differ between each other in restrictions such as that boxes must match only points of the same color (monochromatic) or match only points of distinct colors (bichromatic), or restrictions over the point-set as, for instance, when the points are required to be in general position. We show that some of these problems are hard to solve in polynomial time, but that their optimal solution can be approximated up to constant factors in polynomial time. Finally, we study problems on finding redundancies in the region covered by a set of multidimensional boxes. We consider the Minimum Coverage Kernel problem: given a set B of d-dimensional boxes, find a subset of B of minimum size covering the same region as B. This problem is NP-hard, but as for many NP-hard problems on graphs, the problem becomes solvable in polynomial time under restrictions on the graph induced by the pairwise intersections of the boxes in B. We consider various classes of graphs, show that the Minimum Coverage Kernel problem remains NP-hard even for severely restricted instances, and provide two polynomial-time approximation algorithms for this problem.El estudio de las interacciones entre cajas multi-dimensionales (es decir, hiperrectángulos d-dimensionales alineados a los ejes) ha encontrado aplicaciones en distintas áreas, incluyendo geometría computacional, bases de datos, teoría de grafos y redes. Esta tesis considera varias preguntas abiertas sobre este tema, enfocándose en tres materias fundamentales: el cálculo de emparejamientos de un conjunto de puntos con cajas, la detección de redundancias en la región cubierta por un conjunto de cajas, y el cálculo de distintas medidas de dicha región. Se estudia la complejidad computacional de tres grupos respectivos de problemas, tanto en el peor caso, como dentro del marco de análisis adaptativos. Primero se consideran problemas sobre el cálculo de distintas medidas de la región del espacio cubierta por un conjunto B de cajas. Se introduce el problema de calcular la distribución de profundidad de B, que generaliza el cálculo de su medida de Klee y su profundidad máxima, respectivamente. Se describen distintos algoritmos para calcular la distribución de profundidad de un conjunto de cajas, y se prueban cotas computacionales superiores refinadas para los problemas de calcular la medida de Klee y la profundidad máxima de B, respectivamente, considerando distintas medidas de dificultad de las instancias de estos problemas. Además, se demuestran distintas cotas inferiores condicionales para el problema de calcular la distribución de profundidad, que ayudan a entender su relación con otros problemas fundamentales en la computación. Luego, se estudian distintos problemas sobre el cálculo de emparejamientos de pares de puntos coloreados en un conjunto finito mediante cajas. Un emparejamiento con cajas de un conjunto finito S de puntos, es un conjunto de cajas cerradas, disjuntas dos a dos, y tales que cada caja contiene exactamente dos puntos de S. Los problemas que esta tesis considera difieren entre sí en restricciones tales como que las cajas deban emparejar solo a puntos del mismo color (llamados emparejamientos monocromáticos) o contener solo puntos de distintos colores (llamados emparejamientos bicromáticos), o restricciones sobre el conjunto de puntos, por ejemplo, que se requiera que estén en posición general. Se muestra que algunos de estos problemas son difíciles de resolver en tiempo polinomial, pero que sus soluciones óptimas se pueden aproximar hasta factores constantes en tiempo polinomial. Finalmente, se consideran problemas sobre la eliminación de redundancias en la región del espacio cubierta por un conjunto de cajas multi-dimensionales. Se estudia el problema de encontrar un kernel de cobertura de tamaño mínimo, que consiste en, dado un conjunto B de cajas d-dimensionales, encontrar un subconjunto de B de tamaño mínimo que cubra la misma región que B. Este problema es NP-difícil, pero como muchos problemas NP-difícil sobre grafos, se puede resolver en tiempo polinomial bajo distintas restricciones sobre el grafo inducido por B. Esta tesis considera varias clases de grafos, y muestra que el problema de encontrar un kernel de cobertura de tamaño mínimo sigue siendo NP-difícil incluso para instancias severamente restringidas; y proporciona dos algoritmos de aproximación en tiempo polinomial para este problema.PFCHA-BecasPFCHA-Becas