Resumen de L-corredor k-cromático

C. Bautista Santiago, Javier Cano Vila, J.M. Díaz Báñez, H. González Aguilar, D. Lara, J. Uruttia

• 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.