Problemas de etiquetado: complejidad computacional

• Autores: Pedro Reyes Columé
• Directores de la Tesis: Mª de los Angeles Garrico Vizuete (dir. tes.) , Alberto Márquez Pérez (dir. tes.)
• Lectura: En la Universidad de Sevilla ( España ) en 2002
• Idioma: español
• Tribunal Calificador de la Tesis: Inmaculada Pérez de Guzmán Molina (presid.) , Mario Carlos Machado Jesús (secret.) , Clara Isabel Grima Ruiz (voc.) , Claudia Iturriaga Velázquez (voc.) , María José Chávez de Diego (voc.)
• Enlaces
  • Tesis en acceso abierto en: Idus
• Resumen

  • El etiquetado es una de las grandes áreas de investigación dentro de la Geometría Computacional. Así lo avalan 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 y el gran número de conferencias y encuentros que sobre 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, de forma que cada etiqueta puede ser colocada de forma que el punto quede situado a 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 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 qu