Tolerancia de Estructuras Geométricas y Combinatorias

Ramos Alonso, Pedro A. (1995). Tolerancia de Estructuras Geométricas y Combinatorias. Tesis (Doctoral), Facultad de Informática (UPM) [antigua denominación].

Descripción

Título: Tolerancia de Estructuras Geométricas y Combinatorias
Autor/es:
  • Ramos Alonso, Pedro A.
Director/es:
  • Abellanas Oar, Manuel
  • Hurtado Díaz, Fernando A.
Tipo de Documento: Tesis (Doctoral)
Fecha: 1995
Materias:
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (5MB) | Vista Previa

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, pues valores grandes de la tolerancia garantizan que la solución es estable bajo pequeños errores en los datos. La tolerancia es también útil en el mantenimiento dinámico de estructuras asociadas a objetos en movimiento, pues permite discretizar el problema en intervalos de tiempo en los que la estructura se conserva. 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, que pretende preservar sólo una parte de la estructura, o la región de estabilidad, donde las perturbaciones afectan a un único punto del conjunto. 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 de los ejemplos se muestra que los algoritmos son asintóticamente óptimos. Posteriormente, se estudian los arreglos de segmentos, mostrando cómo se puede calcular la tolerancia de esta estructura combinatoria y aplicando este resultado al cálculo de la tolerancia de la simplicidad de un polígono. Finalmente, se muestra cómo el concepto de tolerancia sirve para definir una medida de calidad para las soluciones de un problema: si para un cierto problema existe más de una solución, la de mayor tolerancia puede ser definida como la mejor. La tolerancia de una propiedad también nos permitirá definir medidas asociadas a la morfología, como medidas de convexidad y simplicidad de un polígono. Este enfoque plantea los llamados problemas de optimización, área en la que aparecen los problemas de mayor dificultad. Abstract In this thesis we introduce the concept of tolerance of a structure or property, combinatorial or geometric, associated to a set S. The tolerance of a structure or property is a measure of stability of the structure or property under perturbations of S. The computation of tolerance can be useful when input data are subjected to errors, because a big tolerance guarantees that the solution is stable under small errors in data. The tolerance is also useful in dynamic maintenance of structures associated with moving objects, because it allows us to discretize the problem in intervals of time such that the structure has no changes. The work begins with the computation of the tolerance of the Delaunay triangulation of a set of points; this structure is also used for exemplifying other concepts related to tolerance, such as local tolerance, which seeks to preserve a part of the structure, or the stability región, where perturbations involve a single point of the set. Next, we study other examples of proximity graphs, mostly the euclidean minimum spanning tree of a set of points and the all nearest neighbors graph. In all cases, we give algorithms which compute the tolerance in the same asymptotic time than the graph itself and in most cases we show that the algorithms are asymptotically optimal. Later, we study arrangements of segments, we show how to compute the tolerance of the combinatorial structure and apply the result to the computation of the tolerance of the simplicity of a polygon. We end showing how the concept of tolerance can be used for defining a measure of quality for solutions of a problem: if a given problem has more than one solution, the one with the biggest tolerance can be defined as the better one. The tolerance of a property allows us to define measures associated to morfology, namely, measures of convexity and simplicity of a polygon. This approach raises optimization problems, that turn out to be the most difficult ones.

Más información

ID de Registro: 10100
Identificador DC: http://oa.upm.es/10100/
Identificador OAI: oai:oa.upm.es:10100
Depositado por: Archivo Digital UPM 2
Depositado el: 19 Ene 2012 07:30
Ultima Modificación: 20 Abr 2016 18:21
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM