L-corredor k-cromático

• C. Bautista-Santiago ^[2] ; J. Cano-Vila ^[2] ; J. M. Díaz Báñez ^[1] ; H. González Aguilar ^[2] ; D. Lara ^[2] ; J. Uruttia ^[2]
  1. [1] Universidad de Sevilla

     Universidad de Sevilla

     Sevilla, España

     
  2. [2] UNAM
• Localización: XIII Encuentros de Geometría Computacional: Zaragoza, del 29 de junio al 1 de julio de 2009 / Alfredo García Olaverri (ed. lit.) , Javier Tejel Altarriba (ed. lit.) , 2009, ISBN 978-84-92774-11-1, págs. 243-249
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • Sea S un conjunto k-coloreado de n puntos en posición general en el plano, k n. Decimos que una región en el plano es k-coloreada, con respecto a S, si esta contiene al menos un punto de cada color. Sea p = (a, b) un punto en el plano, definimos C+ p = {(x, y) : a x, b y} y C− p = {(x, y) : a < x, b < y}. Un L-corredor es un conjunto del plano de la forma C+ p \C− q tal que p = (a, b) y q = (c, d) con a < c y b < d. En este trabajo proponemos un algoritmo con complejidad O(n2 log k) que resuelve el problema de calcular el L-corredor k-cromático que minimice (c−a), bajo la condición que (c−a) = (d−b). Además, damos un algoritmo de complejidad O(n2k) que encuentra el L-corredor k-cromático, tal que este minimiza la suma de (c − a) + (d − b). Así también, consideramos el problema donde el L-corredor k-cromático no tiene una orientación fija, y proporcionamos un algoritmo con complejidad O(n3 log n) para poder encontrarlo.