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.

Programa de la Comunidad Europea "Training and Mobility for Researchers", bajo el proyecto FMRX-CT96-0055

La ansiedad bibliotecaria (AB) es el estado de incertidumbre que experimentan algunos usuarios cuando acuden a la biblioteca, cuyo estudio comenzó en los años 80, pero que carece de un análisis métrico actualizado. El objetivo de este estudio fue hacer un análisis bibliométrico y cienciométrico de los artículos sobre AB indizados en la base de datos Scopus entre 1989 y 2018. Se analizaron 118 publicaciones según indicadores de producción, colaboración, impacto y mapas bibliométricos. Se encontró que las publicaciones sobre AB han aumentado progresivamente, que la colaboración de autores fue baja, que una revista influyente en el área fue Library Review, y que los autores con más impacto fueron Onwuegbuzie y Jiao. Asimismo, destacaron palabras clave sobre la formación del usuario y cuatro frentes de investigación: instrumentos de medición, resultados, marcos teóricos y tipos de unidades de análisis. Dichos resultados sugieren que la AB es un tema fructífero de investigación. / Library anxiety (LA) is the state of uncertainty experienced by some users when they come to the library, the study of which began in the 1980s but lacks updated metric analysis. The objective of this study was to make a bibliometric and scientometric analysis of the articles on LA indexed in the Scopus database between 1989 and 2018. 118 publications were analyzed according to indicators of production, collaboration, impact and bibliometric maps. It was found that publications on LA have progressively increased, that the collaboration of authors was low, that an influential journal in the area was Library Review, and that the authors with the greater impact were Onwuegbuzie and Jiao. Also, keywords on user training and four research fronts were highlighted: measurement instruments, results, theoretical frameworks and types of analysis units. These results suggest that LA is a fruitful research topic. / Revisón por pares