Problemas de etiquetado complejidad computacional

Abstract

El etiquetado es una de las grandes áreas de investigación dentro de la Geometría Computacional. Así lo avalan, tanto la gran cantidad de trabajos que, motivados por sus aplicaciones en diferentes áreas como la cartografía, se elaboran por parte de la comunidad científica internacional, como el gran número de conferencias y encuentros que sob re la materia se realizan periódicamente. Este interés queda refrendado por el hecho de que la ACM lo incoropora como área preferente de investigación dentro del campo de la Geometría Computacional. Dentro de este campo, y debido a la enorme complejidad de sus problemas, aparecen multitud de variantes del problema general. Una de estas variantes es la consistente en el etiquetado de puntos con etiquetas rectangulares. Esta variante presenta dos modelos: etiquetado con etiquetas fijas, donde cada etiqueta puede ser colocada en un número finito de puntos y etiquetado con etiquetas deslizantes, donde cada etiqueta puede ser colocada de forma que el punto quede situado en cualquiera de los puntos del contorno de la etiqueta. En numerosos problemas de etiquetado (redes de metro, mapas de carretera) los puntos a etiquetar son alineados. Estos modelos de etiquetado son el objeto de estudio de la primera parte de la memoria, donde se estudiará la complejidad computacional de los distintos problemas que se pueden plantear, tanto cuando los puntos estén situados sobre una línea horizontal, como cuando lo estén en una línea oblicua. Estudiaremos, en esta primera parte, tanto los problemas de decisión como los correspondientes problemas de optimización del tamaño de las etiquetas. Motivado por la naturaleza NP-dura de uno de estos problemas (el correspondiente a etiquetados de puntos alineados sobre una línea horizontal con etiquetas rectangulares deslizantes) y de otro problema de etiquetado (etiquetado con etiquetas rectangulares de área mínima y vértices prefijados) y la relación de estos problemas que da origen a todos ellos (problema de conexión de parejas con puntos trazados ortogonales), en la segunda parte de la memoria presentaremos algoritmos de aproximación para estos problemas de optimización del número de etiquetas. Realizaremos esta aproximación, tanto mediante algoritmos deterministas, como mediante el uso de los algoritmos genéticos, con la particularidad de que la codificación presentada es la misma para los tres problemas, a pesar de que los problemas de decisión asociados a cada uno de ellos son de distinta naturaleza, ya que uno de ellos es polinomial y los otros dos son NP-completos, siendo uno de ellos fuertemente NP-completo, mientras que el otro admite un algoritmo pseudo-polinomial.