Doctor en Ciencias, Mención Computación / 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.

En esta tesis, el algoritmo de SLAM localización y mapeo simultáneoha sido integrado con técnicas de planificación, con el fin de obtener trayectorias para vehículos terrestres en ambientes exteriores. El algoritmo de SLAM permite que el vehículo obtenga una representación del ambiente en un mapa variante en el tiempo al que podrían asociarse múltiples capas de datos, donde estas capas pueden incluir información diversa tal como: presencia de obstáculos, pendiente o altura del terreno, tipo de suelo, etc. Este mapa es dividido en regiones con alta correlación interna utilizando técnicas de geometría altamente eficientes desde el punto de vista computacional, con estructuras de datos y abstracciones que permitan manejar grandes cantidades de información. Estas regiones a su vez son divididas logrando una resolución en dos niveles de la información. Una que se denomina global y divide a todo el mapa conocido, y otra local que fracciona cada una de esas regiones. Con esta representación del ambiente, o en forma simultánea con la adquisición de ésta, es posible hallar trayectorias mediante técnicas de planificación. Con este fin, se definen criterios que permitan utilizar en la plani-ficación las múltiples capas de información permitiendo la utili-zación de cualquier algoritmo existente para este propósito. Esta aproximación permite lograr un algoritmo que es más eficiente que cualquier algoritmo de planificación existente para ambientes en exploración como se enfrentan en aplicio-nes de SLAM. Finalmente, como ejemplo de la estrategia propuesta, se generan trayectorias a partir de un modelo cinemático de un vehículo de cuatro ruedas y una estrategia de control. Se elige la velocidad lineal deseada del vehículo y se observa la limitación en el ángulo de giro del volante, con el objetivo de evaluar el desempeño del mismo mediante simulaciones numéricas y datos experimentales. / In this thesis, the SLAM algorithm Simultaneous Localization and Mapping has been integrated with planning strategies in order to achieve trajectories for land vehicles in outdoor environments. The SLAM algorithm allows the vehicle to obtain a representation of the environment in a time varying map. This time varying map could contain multiple layers of information, where these layers may include many types of data such as obstacles, slope or height of the terrain, etc. The map is divided into regions that have a high correlation using computational geometry techniques, which are highly efficient from the computational point of view. Towards this end, data structures and abstractions which can handle a significant amount of data are defined. Additionally, these regions are divided achieving two levels of inform: global and local. At global level, the whole known map is divided and at local level, each region is partitioned. Either once the repre-sentation of the environment is achieved or simultaneously with this process, it is possible to find trajectories using planning techniques. Criteria are defined to make use of the multiple layers of information at the planning stage and a particular type of planning algorithm is used, but there is a wide range of possible algorithms. This approach allows to achieve an algorithm that is more efficient than any existing planning algorithm for environments under exploration. Finally, to exemplify the proposed strategy, a kinetic model of a carlike vehicle is used with a control strategy to obtain trajectories. In these trajectories, the speed of the vehicle is chosen roughly constant and the limits of the steering angle are observed. The performance of the whole scheme is assessed through numerical simulations and experimental data.

No description available.

Esta tesis se divide en dos partes. La primera parte contiene el estudio de tres pesos o profundidades, asociados a conjuntos finitos de puntos en el plano: el peso definido por las capas convexas, convex depth (introducido por Hubert (72) y Barnett (76)), la separabilidad lineal, también conocido por location, halfspace o Tukey depth (Tukey 75) y el peso Delaunay (Green 81). De la noción de peso, se obtiene una estratificación de los conjuntos de puntos en el plano en capas y una partición del plano en regiones o niveles, cuyas fronteras son conocidas por depth contours. Se definen los conceptos de capa y nivel en los tres pesos señalados y se estudian sus propiedades y complejidades. Chazelle obtuvo métodos para hallar en tiempo óptimo las capas convexas, que coinciden con las fronteras de los niveles convexos. En esta tesis, para los pesos de separabilidad lineal y Delaunay, se proporcionan algoritmos de obtención, tanto de capas como de niveles, y de cálculo del peso de un punto nuevo que se incorpore a la nube. De forma independiente, han sido obtenidos para el peso de la separabilidad lineal los algoritmos de construcción de los niveles, location depth contours, y el de cálculo del peso de un punto nuevo, por Miller et al. (01). Para los tres pesos mencionados, se analizan árboles generadores, poligonizaciones o triangulaciones, con peso mínimo, donde el peso se ha considerado como la suma de los pesos de las aristas de dichas estructuras. Se obtienen propiedades generales entorno a la caracterización de tales estructuras y algoritmos de obtención para alguna de ellas. Se definen dos pesos relacionados con la separabilidad mediante cuñas: el peso según dominación isotética y la separabilidad . En ambos, se dan algoritmos para el cálculo de los pesos de los puntos de un conjunto dado. La separabilidad  está estrechamente relacionada con la enumeración eficiente de (,k)-sets. Se realiza un estudio combinatorio del conjunto de (,k)-sets para nubes de puntos en el plano y se describen algoritmos de construcción de todos los (,k)-sets en cada uno de los cuatro casos posibles, según sean,  o k, fijos o variables. En la segunda parte, se tratan diversos problemas de transversalidad. Se obtienen resultados acerca de la caracterización de las permutaciones realizables, tanto como polígonos simples, como convexos, sobre arreglos de rectas. Para colecciones de segmentos en el plano, se definen cuña y círculo transversales separadores. Se realiza un análisis del orden de estos elementos transversales separadores y se obtienen diversos algoritmos de decisión de existencia de los mismos y construcción de todos ellos. Para colecciones de círculos, también se define el círculo transversal separador y se obtiene un algoritmo de existencia y construcción de dichos círculos para círculos con el mismo radio. / This thesis can be divided into two parts. The first part contains the study of three weights or depths associated to finite point sets in the plane: the convex depth convex hull peeling depth (introduced by Hubert (72) and Barnett (76)), the location depth (also known by halfspace or Tukey depth (Tukey (75)), and the Delaunay depth (Green (81)).From any notion of depth, a stratification of the point sets of the plane into layers and a partition of the plane into regions or levels are obtained. The boundaries of the levels are known by depth contours. We define the concepts of layers and levels for all three depths and we study their properties and their complexities. Chazelle obtained methods to find the layers, which are the boundaries of the convex levels, with an optimal time algorithm. We present the algorithms for constructing the layers and levels, in location and Delaunay depths. Also, for both depths, we show algorithms to calculate the depth of a new point joining the cloud. In an independent way, the algorithms to obtain the levels (location depth contours) and to calculate the location depth of a new point, are obtained by Miller et al. (01).For each one of the three mentioned depths, we study the geometric structures (spanning trees, polygonizations and triangulations) with minimum weight, where this weight has been considered as t-weight (the addition of the weight of their edges). We obtain general properties about the characterization of such structures and some algorithms to obtain them. We define two depths related with the separability by wedges: the isothetic-domination and the -separability which generalizes the location depth. We develop the algorithms in order to obtain the depths of all points of a given set in both cases. The -separability (in particular the location depth) is closely related with the efficient enumeration of the (,k)-sets. We make a combinatorial study of the (,k)-sets for point sets in the plane. We give lower and upper bounds for the maximum number of the (,k)-sets and we give algorithms for constructing all them, in each one of the four cases according to the case where  or k are fixed or variable.In the second part, we consider some transversality problems. We obtain results about the characterization of the realizable permutations both as simple and as convex polygons, over arrangements of lines. We also study some transversality problems with wedges and circles. We have defined the separating transversal wedge and the separating transversal circle for sets of segments. We analyze the size of the set of the transversal elements. Furthermore, we obtain some decision algorithms on the existence and construction of all of them. Finally, we define also the separating transversal circle for sets of circles and we obtain an algorithm for sets of circles with the same radius.