Tesis Doctorales UPM: Consulta online

Resumen: En esta tesis se introduce el concepto de tolerancia de una estructura o propiedad, geométrica o combinatoria, definida sobre un cierto conjunto S. La tolerancia es una medida de la estabilidad de dicha estructura o propiedad bajo perturbaciones del conjunto S. El cálculo de la tolerancia es útil cuando los datos de entrada están sujetos a errores o en el mantenimiento dinámico de estructuras asociadas a objetos en movimiento. El trabajo comienza con el cálculo de la tolerancia de la triangulación de Delaunay de un conjunto de puntos; esta estructura se utiliza también para ejemplificar variantes del concepto de tolerancia, como la tolerancia local o la región de estabilidad. A continuación se estudian más ejemplos de grafos de proximidad, siendo de particular importancia el árbol generador mínimo euclídeo de un conjunto de puntos y el grafo de todos los vecinos más cercanos. En todos los casos se dan algoritmos que permiten el cálculo de la tolerancia en el mismo tiempo asintótico que el propio grafo y en la mayoría se demuestra que son asintóticamente óptimos. Finalmente, se muestra cómo el concepto de tolerancia sirve para definir una medida de calidad para las soluciones de un problema: la de mayor tolerancia a perturbaciones.