Tesis:
Problemas geométricos de localización.
- Autor: CALATAYUD RAMOS, Aymee
- Título: Problemas geométricos de localización.
- Fecha: 2004
- Materia: Sin materia definida
- Escuela: FACULTAD DE INFORMATICA
- Departamentos: MATEMATICA APLICADA (FACULTAD DE INFORMATICA)
- Acceso electrónico: http://oa.upm.es/36392/
- Director/a 1º: ABELLANAS OAR, Manuel
- Director/a 2º: GARCIA LOPEZ DE LA CALLE, Jesús
- Resumen: En esta memoria estudiamos problemas geométricos relacionados con la Localización de Servicios, La Localización de Servicios trata de la ubicación de uno o más recursos (radares, almacenes, pozos exploradores de petróleo, etc.) de manera tal que se optimicen ciertos objetivos (servir al mayor número de usuarios posibles, minimizar el coste de transporte, evitar la contaminación de poblaciones cercanas, etc.) La resolución de este tipo de problemas de la vida real da lugar a problemas geométricos muy interesantes. En el planteamiento geométrico de muchos de estos problemas los, usuarios potenciales del servicio son representados por puntos mientras que los servicios están representados por la figura geométrica que mejor se adapta al servicio prestado: un anillo para el caso de radares, antenas de radio y televisión, aspersores, etc., una cuña sí el servicio que se quiere prestar es de iluminación, por ejemplo. Estas son las figuras geométricas con las que hemos trabajado. En nuestro caso el servicio será sólo uno y el planteamiento formal del problema es como sigue: dado un anillo o una cuña de tamaño fijo y un conjunto de n puntos en el plano, hallar cuál tiene que ser la posición del mismo para que se cubra la mayor cantidad de puntos. Para resolver estos problemas hemos utilizado arreglos de curvas en el plano. Los arreglos son una estructura geométrica bien conocida y estudiada dentro de la Geometría Computacional. Nos hemos centrado en los arreglos de curvas de Jordan no acotadas que se cortan dos a dos en a lo sumo dos puntos, ya que estos fueron los arreglos con los que hemos tenido que tratar para la resolución de los problemas. De entre las diferentes técnicas para la construcción de arreglos, hemos estudiado el método incremental, ya que conduce a algoritmos más sencillos desde el punto de vista de la codificación. Como resultado de este estudio hemos obtenido nuevas cotas que mejoran la complejidad del tiempo de construcción de estos arreglos con algoritmos incrementales. La nueva cota O(nlambda3(n)) supone una mejora respecto a la cata conocida hasta el momento: O(nlambda4(n)). También hemos visto que en ciertas condiciones estos arreglos pueden construirse en tiempo O(nlambda2(n)) que es la cota óptima para la construcción de estos arreglos. Restringiendo el estudio a curvas específicas hemos obtenido que los arreglos de n circunferencias de k radios diferentes pueden construirse en tiempo O(n2 min(log(k),alfa(n))), resultado válido también para arreglos de elipses parábolas o hipérbolas de tamaños diferentes cuando las figuras son todas isotéticas.