Tolerancia de Estructuras Geométricas y Combinatorias

Ramos Alonso, Pedro A. (1995). Tolerancia de Estructuras Geométricas y Combinatorias. Thesis (Doctoral), Facultad de Informática (UPM).

Description

Title: Tolerancia de Estructuras Geométricas y Combinatorias
Author/s:
  • Ramos Alonso, Pedro A.
Contributor/s:
  • Abellanas Oar, Manuel
  • Hurtado Díaz, Fernando A.
Item Type: Thesis (Doctoral)
Date: 1995
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (5MB) | Preview

Abstract

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.

More information

Item ID: 10100
DC Identifier: http://oa.upm.es/10100/
OAI Identifier: oai:oa.upm.es:10100
Deposited by: Archivo Digital UPM 2
Deposited on: 19 Jan 2012 07:30
Last Modified: 20 Apr 2016 18:21
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM