Autor: RAMOS ALONSO, Pedro Antonio

Título: Tolerancia de estructuras geométricas y combinatorias.

Fecha: 1995

Materia: Sin materia definida

Escuela: FACULTAD DE INFORMATICA

Departamento: MATEMATICA APLICADA (FACULTAD DE INFORMATICA)

Acceso electrónico: http://oa.upm.es/10100/

Director/a(s):

• Director/a: HURTADO DIAZ, Fernando Alfredo
• Director/a: ABELLANAS OAR, Manuel

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.