Resumen de Diseño y análisis de algoritmos para localización y trazado de trayectorias
SE ABORDAN EN ESTA TESIS LOS DOS PROBLEMAS SIGUIENTES: 1, DADA UNA REGION DE TRABAJO Y DADO UN CONJUNTO DE OBSTACULOS CONTENIDOS EN ELLA, AVERIGUAR SI ES POSIBLE LA LOCALIZACION DE UN OBJETO EN UNA POSICION DETERMINADA. 2.
DADA UNA REGION DE TRABAJO Y DADO UN CONJUNTO DE OBSTACULOS CONTENIDOS EN ELLA, AVERIGUAR SI EXISTE UNA TRAYECTORIA ENTRE DOS POSICIONES DADAS DE UN MOVIL, OBTENIENDO EN CASO AFIRMATIVO LA TRAYECTORIA DE LONGITUD MINIMA.
ESTOS DOS PROBLEMAS SE CONSIDERAN EN SITUACIONES EN QUE INTERVIENE LA CONDICION GEOMETRICA DE MONOTONIA, PERMITIENDO OBTENER RESULTADOS SATISFACTORIOS EN EL TIEMPO DE COMPUTACION NECESARIO PARA SU RESOLUCION.
EL AMBITO EN QUE SE DESARROLLA LA TESIS ES EL DE LA GEOMETRIA COMPUTACIONAL ENTENDIENDO COMO TAL EL DISEÑO Y ANALISIS DE ALGORITMOS GEOMETRICOS.
SE UTILIZA A LO LARGO DE TODA LA TESIS COMO MODELO TEORICO DE COMPUTACION EL RAM REAL, Y LOS ANALISIS DE LOS 24 ALGORITMOS PRESENTADOS SE REALIZAN RESPECTO AL TIEMPO ASINTOTICO.
SON DE DESTACAR LOS SIGUIENTES RESULTADOS:
LA INTERSECCION DE CADENAS MONOTONAS SE OBTIENE EN UN TIEMPO LINEAL RESPECTO DEL NUMERO TOTAL DE VERTICES DE ESTAS. (CAPITULO 1).
EL CALCULO DEL D-ENTORNO DE UNA CLASE DE POLIGONOS, COMO SON LOS POLIGONOS SIMPLE-EXTERNAMENTE-VISIBLES (SEV), SE REALIZA EN UN TIEMPO LINEAL RESPECTO AL NUMERO DE SUS VERTICES. ESTE RESULTADO PERMITE OBTENER UN BUEN ALGORITMO PARA LOCALIZACION DE OBJETOS CIRCULARES ENTRE OBSTACULOS. (CAPITULOS 2 Y 3).
LA CONDICION DE MONOTONIA, MAS DEBIL QUE LA DE CONVEXIDAD, ES SUFICIENTE PARA OBTENER ALGORITMOS LINEALES EN EL TIEMPO DE EJECUCION PARA EL TRAZADO DE TRAYECTORIAS EVITANDO COLISIONES. (CAPITULO 4).
