<< Volver atrás

Tesis:

Diseño y análisis de algorítmos para localización y trazado de trayectorias

  • Autor: LODARES GONZALEZ, Dolores

  • Título: Diseño y análisis de algorítmos para localización y trazado de trayectorias

  • Fecha: 1989

  • Materia: MATEMÁTICAS. Teseo;CIENCIAS DE LA COMPUTACIÓN. Teseo;LENGUAJES ALGORÍTMICOS. Teseo

  • Escuela: FACULTAD DE INFORMATICA

  • Departamentos: SIN DEPARTAMENTO DEFINIDO

  • Acceso electrónico:

  • Director/a 1º: ABELLANAS OAR, Manuel

  • Resumen: Se abordan en esta tesis los dos problemas siguientes: 1. Dada una región de trabajo y dado un conjunto de obstáculos contenidos en ella, averiguar si es posible la localización de un objeto en una posición determinada. 2. Dada una región de trabajo y dado un conjunto de obstáculos contenidos en ella, averiguar si existe una trayectoria entre dos posiciones dadas de un móvil, obteniendo en caso afirmativo la trayectoria de longitud mínima. Estos dos problemas se consideran en situaciones en que interviene la condición geométrica de monotonía, permitiendo obtener resultados satisfactorios en el tiempo de computación necesario para su resolución. El ámbito en que se desarrolla la tesis es el de la geometría computacional entendiendo como tal el diseño y análisis de algorítmos geométricos. Se utiliza a lo largo de toda la tesis como modelo teórico de computación el RAM real, y los análisis de los 24 algorítmos presentados se realizan respecto al tiempo asintótico. Son de destacar los siguientes resultados: la intersección de cadenas monótonas se obtiene en un tiempo lineal respecto del número total de vértices de estas. (Capitulo 1). El cálculo del d-entorno de una clase de polígonos, como son los polígonos simple-externamente-visibles (sev), se realiza en un tiempo lineal respecto al número de sus vértices. Este resultado permite obtener un buen algorítmo para localización de objetos circulares entre obstáculos. (Capítulos 2 y 3). La condición de monotonía, más débil que la de convexidad, es suficiente para obtener algorítmos lineales en el tiempo de ejecución para el trazado de trayectorias evitando colisiones. (Capítulo 4)