Juego de Voronoi Manhattan

JUEGO DE VORONOI MANHATTAN Luis Vallejo Hermosilla Memoria presentada como parte de los requisitos para la obtención del título de Grado en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Pablo Sebastián Alegre Rueda Prof. Alfonso Carriazo Rubio 9 de julio de 2024 Índice general Resumen ..................................... 1 Abstract...................................... 1 1. Introducción 3 2. Preliminares 9 2.1. Diagramas de Voronoi con la distancia L2................ 9 2.1.1. Diagramas de Voronoi en todo R2................ 9 2.1.2. Diagramas de Voronoi acotados . . . . . . . . . . . . . . . . . 11 2.1.3. Diagramas de Voronoi en Rm.................. 11 2.2. Diagramas de Voronoi en R2con la métrica L1............. 12 2.2.1. Mediatrices en la métrica L1................... 13 2.2.2. Diagramas de Voronoi Manhattan . . . . . . . . . . . . . . . . 15 2.2.3. Semipolígonos y divisiones . . . . . . . . . . . . . . . . . . . 17 3. Conjuntos de puntos balanceados 21 3.1. Conceptos básicos y caracterización . . . . . . . . . . . . . . . . . . . 21 3.2. Configuraciones básicas de puntos que no forman una cuadrícula . . 23 ii juego de voronoi manhattan 3.2.1. Conjuntos balanceados de dos puntos . . . . . . . . . . . . . 24 3.2.2. Conjuntos balanceados de tres puntos . . . . . . . . . . . . . 26 3.2.3. Otras configuraciones básicas balanceadas de más de tres puntos 28 3.3. Configuraciones no básicas . . . . . . . . . . . . . . . . . . . . . . . . 29 4. Juego de Voronoi Manhattan a una ronda 33 4.1. Existencia de estrategia ganadora para Black . . . . . . . . . . . . . . 35 4.2. Propiedades y características de los conjuntos invencibles . . . . . . . 40 5. Otras variantes del Juego de Voronoi, problemas relacionados y problemas abiertos 57 5.1. Variantes y problemas relacionados con el Juego de Voronoi . . . . . 57 5.2. Problemas y líneas de investigación abiertas . . . . . . . . . . . . . . 60 Bibliografía 61 Resumen El presente trabajo tiene como objetivo el análisis del artículo [4] sobre el Juego de Voronoi a una ronda con la distancia Manhattan, a fin de esclarecer y complementar los contenidos que en él se tratan. En esta variante del juego, dos jugadores compiten en una región Rrectangular de altura 1y base ρ, donde primero colocan npuntos cada uno y, posteriormente, se traza el diagrama de Voronoi (usando la distancia Manhattan) de los puntos, consiguiendo cada jugador el área que sumen los polígonos de Voronoi correspondientes a sus puntos. Se estudiarán, en primer lugar, las llamadas configuraciones de puntos balanceadas, las cuales son disposiciones de puntos para las que las celdas de sus diagramas de Voronoi cumplen ciertas propiedades geométricas. Tras ello, se expondrá la anterior mencionada variante del Juego de Voronoi, detallando las posibles estrategias ganadoras que poseen ambos jugadores. Se concluirá que el primer jugador posee una estrategia ganadora si y solo si ρ≥n y juega una disposición de puntos determinada, ganando el segundo jugador cuando ρ<n. Abstract The objective of the following project is the analysis of the article [4] on the One- Round Manhattan Voronoi Game, in order to clarify and complement the contents discussed in it. In this variant of the game, two players compete in a rectangular region Rof height 1and base ρ, where they first place npoints each and then the Voronoi diagram is drawn (using the Manhattan distance), scoring each player the area added up by the Voronoi polygons corresponding to their points. First of all, the so-called balanced configurations will be studied, which are point arrangements for which the cells of their Voronoi diagrams satisfy certain geometric properties. After that, the aforementioned variant of the Voronoi Game will be presented, detailing the possible winning strategies for both players. It will be concluded that the first player has a winning strategy if and only if ρ≥nand plays a certain arrangement of points, with the second player winning when ρ < n. 1 Introducción Los avances científicos y técnicos que se han dado desde el siglo pasado han contribuido al nacimiento de novedosas y útiles áreas de las matemáticas. Disciplinas que, si bien comenzaron a esbozarse varios siglos atrás, no llegaron a consolidarse como tales hasta mediados y durante la segunda mitad del siglo XX. Es el caso concreto de importantes ramas de hoy día como la Investigación Operativa y la Teoría de Juegos. Trabajos como los de Blaise Pascal (1623-1662) y Christiaan Huygens (1629-1695) acerca del Problema de la partida interrumpida (The problem of points) (consultado en [15]) u otros análisis de estrategias de juegos, como el de Ernst Zermelo (1871-1953), con su obra Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels [Sobre una aplicación de la teoría de conjuntos al juego del ajedrez], en 1913 (citado en [16]) pueden ser ya enmarcados dentro de estas ramas. Sin embargo, no es hasta mediados del siglo pasado, cuando estas disciplinas nacen como tales, debido a la necesidad de optimizar las decisiones durante la Segunda Guerra Mundial, en el caso de la Investigación Operativa, o de la mano de John von Neumann (1903-1957) con su obra Zur Theorie der Gesellschaftsspiele [Sobre la teoría de los juegos de mesa] (1929), en el caso de la Teoría de Juegos, cuyo nacimiento se consolida en 1944 con el libro Theory of Games and Economic Behavior, de John von Neumann y Oskar Morgenstern (1902-1977) (consultado en [18]). Dentro de estas disciplinas estrechamente ligadas se sitúa una importante rama: los problemas de localización o ubicación óptima. En ellos, partiendo de una situación y unas condiciones ya establecidas, se busca elegir una ubicación que sea óptima de acuerdo con las posibilidades disponibles y en base a los criterios de optimalidad establecidos (como, por ejemplo, la distancia). El estudio de estos problemas data de principios del siglo pasado [4], con las aportaciones de Wilhelm Launhardt (1832- 1918) en The Theory of Trace: Being a discussion of the Principles of Location (1900) y de Alfred Weber (1868-1958), con Über den Standort der Industrie [Sobre la localización 4juego de voronoi manhattan de industrias] (1909), donde desarrolla su teoría del Triángulo de localización. Esta serie de problemas y su estudio son de gran interés en campos como el empresarial y el comercial, donde la creciente y rápida globalización de las últimas décadas ha propiciado un entorno mucho más competitivo. Hoy día, las empresas y corporaciones de todo el globo se ven obligadas a optimizar al máximo su toma de decisiones a fin de mantenerse a la vanguardia de sus respectivos sectores, donde la competencia es ya a nivel mundial. Todo ello ha contribuido al desarrollo, dentro del campo de la localización óptima, de los llamados problemas de localización óptima competitivos, tratados por primera vez por Harold Hotelling (1895-1973), en Stability in competition (1929). En este tipo de problemas, dos o más jugadores (que se pueden interpretar como empresas competidoras de un mismo sector, por ejemplo, dos cadenas de supermercados), dentro de un cierto marco de premisas establecido (como que ambos disponen de las mismas oportunidades y recursos), compiten por conseguir estas ubicaciones óptimas. Para nosotros, el problema de interés en cuestión se enmarca en esta disciplina de localización óptima competitiva, dentro de los denominados Juegos de Voronoi (o Juegos Voronoi), introducidos por primera vez en [1]. De gran carácter geométrico, los Juegos de Voronoi consisten en el enfrentamiento de dos jugadores, según diferentes versiones, White y Black, Alice y Bob o, simplemente, Jugador 1 y Jugador 2, dentro de un recinto o área de juego R. En él, los jugadores compiten colocando cada uno (según se establezca en las normas, turnos secuenciales, un solo turno u otra opción) el mismo número de puntos, que pueden ser interpretados como instalaciones, siendo los jugadores empresas competidoras de un mismo sector, en la región R. Cada jugador puntúa, en la mayor parte de las variantes, el área de Rque es más cercana a sus puntos que a los del adversario. Este último criterio de puntuación consiste simplemente en, una vez colocados los puntos de ambos jugadores, trazar el diagrama de Voronoi dentro de Rde las instalaciones de ambos jugadores, de acuerdo a la distancia concreta que se esté utilizando y distinguiendo qué polígonos son de cada jugador atendiendo al punto que lo genera. Otras variantes contemplan la existencia de una serie de clientes o usuarios (que se representan por puntos) distribuidos por el área de juego. En estos casos, se traza también el diagrama de Voronoi de los puntos colocados por ambos jugadores y el objetivo pasa a ser captar un mayor número de clientes con las celdas de los propios puntos que el adversario. En estos casos también puede ser habitual que se busque maximizar el número de clientes influenciados. 1. introducción 5 Los diagramas de Voronoi son construcciones geométricas de gran utilidad que incluso pueden ser observados en estructuras y formaciones de la naturaleza. A grandes rasgos, los diagramas son teselaciones que se construyen a partir de las mediatrices entre los puntos de un conjunto Pdel que se traza el diagrama y son muy útiles para visualizar la proximidad relativa entre los puntos del conjunto Pusado, pudiendo variar además la distancia empleada para trazarlos. Es por ello que son una herramienta muy adecuada para infinidad de campos de estudio como la biología, la medicina, la geología o la planificación urbanística, entre otros muchos. En nuestro caso, son fundamentales en problemas en los que la distancia está fuertemente involucrada, como el caso de los problemas de localización óptima de los que hemos hablado. Al ser estructuras presentes en la naturaleza, es coherente pensar que estos diagramas eran ya familiares desde la antigüedad. El primer uso del que se tiene registro, sin embargo, se remonta a mediados del siglo XVII en Le Monde ou le Trait de la Lumière [El mundo o el Tratado de la Luz] (1644), de René Descartes (1596-1650), donde los diagramas son usados para un estudio cosmológico (consultado en [12]). No es, sin embargo, hasta el siglo XIX que nacen formalmente de la mano del matemático ruso Georgy Feodosevich Voronoi (1868-1908) (o Voronoy, o Voronoï, según traducción) y del matemático alemán Peter Gustav Lejeune Dirichlet (1805-1859) quienes, en sus estudios sobre formas cuadráticas definidas positivas, introducen y estudian estas teselaciones (Dirichlet los casos bi y tridimensionales y Voronoi la generalización m-dimensional, de ahí que estos diagramas suelan llevar su nombre). Figura 1.1: Algunos diagramas usados en Le Monde ou le Trait de la Lumière, de René Descartes. Fuentes: https://www.mediastorehouse.com/p/497/ rene-descartes-vorticies-whirlpools-which-10409774.jpg.webp y https://www.ams.org/featurecolumn/images/august2006/descartes_ voronoi.jpg, respectivamente. 12 juego de voronoi manhattan (a) Diagrama de Voronoi acotado por un compacto S(la frontera es la línea gruesa). Las regiones lila y verde no son convexas, tampoco siendo conexa esta última. (b) Diagrama de Voronoi acotado por una región tal que las celdas son polígonos estrellados con respecto a sus puntos generadores. Figura 2.2 de Voronoi de picomo V or(pi):=\ q∈P\{pi} H(pi, q) Análogamente al caso de R2, se define diagrama m-dimensional de Voronoi como el conjunto V or(P):={V or(p1), ..., V or(pn)}. Observación 2.3.Se permite, en la definición anterior, m= 1, donde los poliedros serían intervalos. En Rm, las fronteras de los poliedros m-dimensionales, ∂V or(pi), son de dimensión m−1. Los diagramas de Voronoi también pueden extenderse a subespacios de Rm, como, por ejemplo, a una esfera o un toro, en el caso de R3, o los diagramas acotados de la subsección anterior en el caso de R2. 2.2 Diagramas de Voronoi en R2con la métrica L1 En esta sección se presentan los conceptos básicos sobre los diagramas de Voronoi usando la distancia Manhattan (métrica L1), en su mayoría análogos a los de la sección 2.1, pues estos diagramas son los que se usarán en prácticamente la totalidad de este trabajo. 2. preliminares 13 Figura 2.3: Diagrama de Voronoi de un conjunto de puntos aleatorio (no todos visibles) en R3. Definición 2.6. Dados dos puntos x= (x1, x2)ey= (y1, y2)del plano, se define la distancia L1en R2(también llamada taxi-distancia odistancia Manhattan), que denotaremos d1, como d1:R2×R2→Rtal que d1(x, y) = |x1−y1|+|x2−y2|. 2.2.1 Mediatrices en la métrica L1 Consideremos dos puntos p= (x(p), y(p)), q = (x(q), y(q)) ∈R2cualesquiera y consideremos, para una distancia cualquiera d, la mediatriz del segmento pq, que denotaremos como B(p, q), esto es, B(p, q):={s∈R2:d(s, p) = d(s, q)}=∂H(p, q), con H(p, q):={s∈R2:d(s, p)≤d(s, q)}. En el caso en el que des la distancia euclídea, la mediatriz de un segmento pq no es más que la recta perpendicular que pasa por el punto medio de pq. Sin embargo, en general, B(p, q)no es una sola línea o ni siquiera es recta. Es, por ejemplo, el caso de la distancia que será usada en este trabajo: la distancia Manhattan. Podemos obtener tres mediatrices distintas usando la distancia d1. La más común consistirá en dos semirrectas (horizontales o verticales) unidas por un segmento de pendiente ±1. Si |x(p)−x(q)|= 0 o|y(p)−y(q)|= 0, entonces el segmento diagonal 14 juego de voronoi manhattan queda reducido a un punto y la mediatriz no es más que una recta horizontal o vertical, respectivamente. El tercer tipo se da cuando |x(p)−x(q)|=|y(p)−y(q)|. En este caso se obtiene una mediatriz que llamamos degenerada, pues esta contiene dos regiones de medida no nula (a las que nos referiremos, en un contexto de competición, como zonas neutrales). Las denominaremos, respectivamente, mediatrices de tipo I,tipo II ytipo III En la Figura 2.4 se muestran estos tres casos. (a) Tipo I: el más usual en la distancia Manhattan. (b) Tipo II: caso |y1−y2|= 0. Para el caso |x1−x2|= 0 sería una recta horizontal. (c) Tipo III: Mediatriz degenerada (|x1−x2|= |y1−y2|). Las zonas rayadas forman parte de la mediatriz y no tienen medida nula. Figura 2.4: Mediatrices posibles para la distancia d1. De ahora en adelante, diremos que una mediatriz no degenerada (mediatrices tipo I y II) es o tiene dirección vertical (horizontal), si contiene segmentos verticales (horizontales), en el caso de ser tipo I, o si es, directamente, una recta vertical (horizontal), en el caso de las de tipo II. Por ejemplo, la mediatriz de la Figura 2.4a es vertical. No 2. preliminares 15 supone problema alguno esta nomenclatura, pues las mediatrices de tipo I están formadas por dos semirrectas que poseen necesariamente la misma dirección, no se da el caso en el que una de ellas sea vertical y la otra horizontal. Más aún, las mediatrices de tipo I son verticales cuando |x(p)−x(q)|>|y(p)−y(q)|y horizontales cuando |x(p)−x(q)|<|y(p)−y(q)|. Si se da la igualdad, la mediatriz es degenerada (tipo III). Observación 2.4.Tanto las medidas que aparecen en la Figura 2.5a, como las de la Figura 2.5b, serán útiles en capítulos posteriores. Vamos a justificar la medida del segmento azul en el caso de la mediatriz vertical. El otro (horizontal) se puede probar de forma análoga o haciendo uso de que ambas son simétricas respecto de la recta {y=x}. Sin pérdida de generalidad, consideramos dos puntos dispuestos (x1, y1),(x2, y2)como se muestra en dicha figura y su mediatriz, que es de tipo I vertical. Sea (t, u)el punto de corte de la mediatriz con el rectángulo de vértices opuestos (x1, y1),(x2, y2), entonces u=y2y la distancia de (t, y2)al vértice superior izquierdo del rectángulo (que es el punto (x1, y2)) es igual a la distancia de x1aten el eje OX, esto es, |x1−t|(pues son puntos con la misma ordenada y2). Por otro lado, como (t, y2)es un punto de la mediatriz, entonces d1((x1, y1),(t, y2)) = d1((x2, y2),(t, y2)), |x1−t|+|y1−y2|=|x2−t|+|y2−y2|, |x1−t|+|y1−y2|=|x2−t|. Sumamos |x1−t|a ambos lados de la igualdad y usamos que |x1−t|+|x2−t|= |x1−x2|, por ser tun punto del intervalo [x1, x2]; 2|x1−t|+|y1−y2|=|x1−x2|, |x1−t|=|x1−x2|−|y1−y2| 2, que es la cantidad que aparece en la Figura 2.5a. 2.2.2 Diagramas de Voronoi Manhattan Definición 2.7. Consideremos un punto pi∈Py los semiplanos H(pi, pj)para cada pj∈P\{pi}. Se define, análogamente al caso de L2, el polígono de Voronoi Manhat- 16 juego de voronoi manhattan (a) Mediatriz tipo I vertical en detalle. Debido a la simetría de la mediatriz, ambos segmentos azules miden lo mismo, esto es, |x1−x2|−|y1−y2| 2. Se deduce que la medida de los segmentos naranjas no es más que |x1−x2|+|y1−y2| 2, azul y naranja deben sumar |x1−x2|. (b) Mediatriz tipo I horizontal en detalle. En este caso, los segmentos azules miden |y1−y2|−|x1−x2| 2y los naranjas |y1−y2|+|x1−x2| 2. Figura 2.5 tan, que denotaremos V orM(pi), como V orM(pi):=\ q∈P\{pi} H(pi, q). Del mismo modo, se define el diagrama de Voronoi Manhattan de P, V orM(P), a la teselación determinada por V orM(pi)i=1,...,n. Figura 2.6: Diagrama de Voronoi Manhattan de seis puntos aleatorios en R2. Cuando no haya confusión, omitiremos la especificación "Manhattan" y el subíndice Mal nombrarlos. 2. preliminares 17 En contraste con los diagramas de Voronoi usando la distancia euclídea, los diagramas de Voronoi Manhattan fallan en dos propiedades que si tenían los primeros: La frontera del diagrama de Voronoi Manhattan, ∂V orM(P), puede poseer zonas de medida positiva (ver Figura 2.4c). En el caso euclídeo, la frontera estaba formada solo por rectas, semirrectas o segmentos. Los polígonos de Voronoi Manhattan no tienen por qué ser convexos, aunque sí son dominios estrellados. Esto no ocurría en el caso euclídeo, donde todos los polígonos de Voronoi eran convexos Ambas propiedades son claras cuando se analizan los tres tipos de mediatrices presentados en la subsección anterior 2.2.1. Trabajaremos con diagramas de Voronoi Manhattan acotados por una región. La definición es análoga a la Definición 2.4 presentada en el caso euclídeo. 2.2.3 Semipolígonos y divisiones En esta subsección se consideran diagramas de Voronoi Manhattan acotados por un compacto S. Definición 2.8. Sea un punto p∈P, consideremos tanto la recta vertical como la horizontal que pasan por p. Estas dividen al polígono V or(p)en dos partes, cada una, a las que llamaremos semipolígonos osemiceldas, En el caso de la recta horizontal, semipolígonos superior e inferior (referidos a veces como semipolígonos horizontales) y, en el caso de la vertical, semipolígonos izquierdo y derecho (también llamados verticales). Además, ambas rectas llevan a una división en cuatro cuadrantes (abiertos) Qi(p), con i= 1, ..., 4. Definiremos, entonces, el i-ésimo cuarto de polígono aCi(p):=V or(p)∩ Qi(p). Además de la división espacial en cuadrantes, si se tienen en cuenta también las dos rectas diagonales de pendiente ±1que pasan por p, obtenemos ahora una división en 8regiones (abiertas) denominadas octantes, que denotaremos por Oi(p), con i= 1, ..., 8. Definición 2.9. Dado un punto p∈P, pueden considerarse las cuatro semirrectas horizontales y verticales que pasan por py su intersección con V or(p), (luego ahora son 18 juego de voronoi manhattan segmentos). A estos cuatro segmentos los denominamos los cuatro brazos de V or(p). Dos brazos distintos diremos que son vecinos si, asignando a los cuatro brazos un orden cíclico (horario o antihorario), aparecen consecutivos; en caso contrario, son brazos opuestos. Nos referiremos como brazo frontera a aquel cuyo punto final está en la frontera de S. En caso contrario, diremos que es interno. Un polígono o celda V or(p)decimos que es un puente si posee dos brazos frontera que sean opuestos. (a) Imagen de un polígono de Voronoi Manhattan para un punto p(rojo). En naranja, el semipolígono superior de V or(p) y en verde y azul los cuartos de polígono C3(p)yC4(p), respectivamente. La división en cuadrantes en líneas discontinuas y en octantes en las líneas anteriores sumando las lineas diagonales punteadas. (b) Diagrama de Voronoi Manhattan de un conjunto de puntos formando una cuadrícula 3×2en una región rectangular (trazo grueso). En línea discontinua verde los brazos frontera y en azul los internos. (c) Un polígono puente coloreado en naranja. Figura 2.7: Definiciones 2.8 y 2.9. El siguiente resultado será de utilidad más adelante; lo enunciaremos en esta subsección. Proposición 2.1.Se cumplen las siguientes propiedades: 2. preliminares 19 1. Sea q∈V or(p). Si la mediatriz B(p, q)es no degenerada (recordemos, tipo I o tipo II) y vertical (horizontal), entonces no interseca a ambos semipolígonos de V or(p)izquierdo y derecho (superior e inferior). 2. Para cada q1, q2∈Oi(p), las mediatrices B(p, q1)yB(p, q2)son no degeneradas y ambas tienen la misma dirección (vertical u horizontal). 3. Todo polígono de Voronoi (Manhattan) está contenido en el rectángulo alineado con los ejes que generan sus brazos. Demostración. Sin pérdida de generalidad, supondremos un sistema coordenado centrado en py las correspondiente división en octantes Oi(p). Las rectas que forman los octantes serían los ejes OX ≡ {y= 0}yOY ≡ {x= 0}y las rectas y=xey=−x. en consecuencia, p= (0,0). Veamos las tres propiedades. 1. Sean un polígono V or(p)y un punto q∈V or(p), de coordenadas (x(q), y(q)). Si la mediatriz B(p, q)es no degenerada, entonces qestá en algunos de los octantes Oi(p)o está en los ejes OX uOY . Si estuviese en el eje OX, entonces B(p, q)sería una recta vertical (pues |y(q)−y(p)|=|0−0|= 0), concretamente la recta x=x(q)/2, luego estaría siempre contenida en el semiplano {x > 0}o{x < 0}y no cortaría al semipolígono izquierdo o derecho, respectivamente. Análogamente si q∈OY . Para los octantes, distinguimos dos casos. Si q∈Oi(p)con i= 1,4,5,8, entonces |x(q)|>|y(q)|lo que implica que |x(q)−0|>|y(q)−0|, luego B(p, q)es una mediatriz tipo I vertical. Tanto las dos semirrectas verticales como el segmento de pendiente ±1están contenidos entre el eje OY y la recta x=x(q), luego contenida en los semiplanos {x > 0}o{x < 0}, por lo que no corta al semipolígono izquierdo o derecho, respectivamente. El caso q∈Oi(p)con i= 2,3,6,7es análogo haciendo los correspondientes cambios. 2. Consideremos dos puntos q1, q2que pertenecen a un mismo octante Oi(p). Asignamos las correspondientes coordenadas q1= (x(q1), y(q1)),q2= (x(q2), y(q2)) y, como ya sabemos, p= (0,0). Como los octantes son regiones abiertas, entonces se tiene que q1, q2/∈ {y=x},{y=−x}, lo cual implica que |x(qi)| = |y(qi)|⇒|x(qi)−0| =|y(qi)−0|,i= 1,2, luego las mediatrices B(p, q1) yB(p, q2)no son degeneradas (es más, tampoco son tipo II porque q1, q2/∈ OX, OY , luego |x(qi)−0| = 0,|y(qi)−0| = 0,i= 1,2). Que las mediatrices B(p, q1)yB(p, q2)tienen misma dirección es claro, pues al pertenecer q1yq2 al mismo octante, ambos puntos cumplen |x(qi)|<|y(qi)|o|x(qi)|>|y(qi)|, i= 1,2⇒ |x(qi)−0|<|y(qi)−0|o|x(qi)−0|>|y(qi)−0|,i= 1,2, 20 juego de voronoi manhattan que se corresponde con, respectivamente, mediatrices de tipo I horizontales o mediatrices de tipo I verticales. 3. Es consecuencia del punto anterior. Por 2., se deduce que los extremos de los brazos de V or(p)se conectan por caminos formados por las mediatrices que conforman la frontera de la celda que son monótonos en las direcciones xe y, pues dos puntos que pertenecen al mismo octante poseen mediatrices del mismo tipo (vertical u horizontal) con p. Esto implica que no es posible, por ejemplo, que el extremo del brazo superior y el del izquierdo estén conectados por una mediatriz horizontal, luego una vertical, y luego otra horizontal. Solo estarán conectados por un tramo de mediatrices horizontales y otro de verticales. Ello implica que estos caminos son, como mucho, un segmento vertical y un horizontal que unen cada par de brazos del polígono, luego V or(p)está contenido en el rectángulo que forman estos brazos, concluyendo la demostración del resultado. □ (a) (b) (c) Figura 2.8: Las tres propiedades de la Proposición 2.1 en un mismo polígono V or(p). 3 Conjuntos de puntos balanceados De ahora en adelante, los polígonos y diagramas de Voronoi que se consideren se construirán con la distancia Manhattan. El objetivo de este capítulo es presentar y estudiar las configuraciones de puntos balanceadas. Este concepto de balanceo surge de la combinación de dos propiedades: ecuanimidad y optimalidad local, que son dos propiedades del campo de la ubicación óptima de instalaciones que definiremos a continuación. Seguidamente estudiaremos las configuraciones básicas y seguiremos con las no básicas (que están formadas por la unión de básicas). Veremos que, a diferencia del caso de la distancia euclídea, donde estas configuraciones llevan a disposiciones de puntos formando cuadrículas ortogonales [8], la variedad en caso de usar la distancia Manhattan es mucho más amplia. 3.1 Conceptos básicos y caracterización Definición 3.1. Decimos que un conjunto de puntos P∈R⊂R2, con Runa región rectangular de altura 1y base ρ, está balanceado si se satisfacen las siguientes dos condiciones: Ecuanimidad: ∀p1, p2∈P, Área(V or(p1)) = Área(V or(p2)). Optimalidad local: ∀p∈P,pes el punto que minimiza la distancia media a todos los puntos de V or(p). La primera surge de manera natural, pues consiste en asignar a cada instalación la 28 juego de voronoi manhattan existe solución, por lo que R3es la única balanceada y queda probado el resultado. □ Figura 3.3: R3, única configuración balanceada posible (salvo simetría) para tres puntos. 3.2.3 Otras configuraciones básicas balanceadas de más de tres puntos A continuación, se presenta una configuración balanceada para el caso en el que |P|= 4, que llamaremos R4y otra cuando |P|= 5, a la que nos referiremos como R5. Probaremos que son balanceadas haciendo uso del Corolario 3.1. Sin embargo, a diferencia de los casos anteriores, aquí no tenemos asegurada que estas sean las únicas. Proposición 3.3.Las configuraciones R4yR5presentadas en la Figura 3.4 representan conjuntos de puntos balanceados. Demostración. Para el caso de R4, todas las celdas son iguales salvo orientación, luego nos centraremos en una de ellas únicamente (la del punto (1/2,1/6), por fijar una). Sus cuartos de polígono son dos rectángulos, ambos de base 2/6y altura 1/6, y dos triángulos rectángulos, ambos de base 2/6y altura 2/6. Se deduce de forma directa, entonces, que todos los cuartos de polígono tienen área 1/18, luego todos los semipolígonos tendrán también misma área. Notemos que el conjunto no suma 1(área total) porque existen cuatro zonas neutrales. 3. conjuntos de puntos balanceados 29 Para el caso de R5, tenemos cuatro polígonos en las esquinas con las mismas áreas y uno central. Calculamos las áreas de los cuartos de celda de los polígonos de las esquinas, fijándonos, por ejemplo, en el de la esquina inferior izquierda. Teniendo en cuenta que los cuatro puntos exteriores de Pforman mediatrices verticales con el punto interior (30/49,1/2), usamos las medidas de la Observación 2.4, quedando las áreas: 18/343 para los cuartos de polígono primero y tercero y 24/343 para segundo y cuarto. En consecuencia, cada semipolígono de estas cuatro celdas de las esquinas tiene área de 6/49. Calculamos ahora las áreas de los cuartos de polígono de la celda central. Como, por simetría, tienen todos la misma área, calcularemos una únicamente. Cada uno de estos cuartos de polígono puede dividirse en un rectángulo de base 2/49 y altura 1/2y un triángulo de base 14/49 y altura 2/7, quedando el área de cada cuarto 3/49, luego cada semipolígono de la celda interior tiene área 6/49, igual que el resto, lo que concluye la prueba. □ Figura 3.4: Configuraciones básicas balanceadas R4yR5. 3.3 Configuraciones no básicas En la sección anterior se trató únicamente con configuraciones de puntos balanceados básicas, que como ya dijimos, eran aquellas que no podían ser descompuestas en subconfiguraciones más pequeñas. Trataremos ahora con configuraciones no básicas, en las que las básicas actuarán como bloques y surgirán configuraciones balanceadas mucho más grandes, obteniéndose familias infinitas de estas. Lo vemos en el siguiente resultado. 30 juego de voronoi manhattan Teorema 3.1. Para cada entero n≥2, existe un rectángulo Ry un conjunto de puntos Ptal que |P|=n,Pes un conjunto balanceado y ningún polígono de Voronoi Manhattan es un rectángulo, esto es, no están sus puntos formando una cuadrícula. Demostración. Para cada n= 3k+5l, con k, l ∈ {0,1, ...}, construimos una configuración combinando kbloques básicos R3ylbloques R5, como se muestra en la Figura 3.5a. El rectángulo Rresultante es de altura 1y base ρ= 1/49(36k+ 60l), atendiendo a las dimensiones de R3(que han sido reescaladas multiplicando por 36/49, para que la base de R3fuese 1) y R5. Se sigue manteniendo la misma área para todos los semipolígonos, pues las áreas de los de R3eran de 49/216 que al reescalar quedan en 6/49, que eran las áreas de los de R5. De esta forma obtenemos configuraciones para n= 3,5,6y para n≥8. Para los casos n= 2,4ya vimos ejemplos en la sección anterior. Alternativamente, haciendo n= 2kcon k∈N, de forma que combinamos k bloques básicos de dos puntos, obtenemos también configuraciones balanceadas para n= 4 y los múltiplos de 2(Figura 3.5b). Para los Ptales que |P|= 3k+ 1, con k∈N, podemos, alternativamente, combinar bloques R4solapándose parcialmente (sin que ello suponga una pérdida de balanceo), como se muestra en la Figura 3.5c. En este último caso está el que faltaba, n= 7.□ Observación 3.1.La última construcción de la prueba (bloques R4parcialmente solapados) es la única de las que se ha visto en la prueba que contiene mediatrices tipo III. De hecho, para el caso n= 7, no se conoce, por el momento, una configuración sin mediatrices de este tipo. 3. conjuntos de puntos balanceados 31 (a) Unión de tres bloques R3y uno R5, resultando un conjunto balanceado de 14 puntos. (b) Disposición de 6 puntos balanceados uniendo tres bloques R2,ρ. (c) Unión de dos bloques R4par- cialmente solapados para formar un conjunto balanceado para n= 7. Figura 3.5 4 Juego de Voronoi Manhattan a una ronda En este capítulo estudiamos en profundidad la variante del Juego de Voronoi sobre la que versa este trabajo: el Juego de Voronoi Manhattan a una ronda (One-Round Manhattan Voronoi Game, en inglés). En este, el área de juego es un rectángulo R⊂R2 que consideraremos, sin pérdida de generalidad, de altura 1y base ρ≥1. Compiten dos jugadores, a los que llamaremos White yBlack, cada uno con npuntos disponibles para colocar en R, a los que llamaremos, en ocasiones, instalaciones. Como vimos en la introducción, haremos uso, para graficar los diagramas de Voronoi, de la distancia Manhattan. Describiremos en su totalidad las estrategias ganadoras y veremos cómo las conclusiones que obtenemos con esta distancia difieren de las que se obtuvieron para la distancia euclídea en [8]. El procedimiento es sencillo: primero White coloca en Rsus npuntos y, seguidamente, hace lo mismo Black (no se dan nturnos secuenciales como en otras variantes). En la Figura 4.1 puede verse un ejemplo para n= 3 puntos. La puntuación de cada jugador consiste en el área de las regiones de Rque están más cerca de sus instalaciones que de las del oponente, i.e., el área de los polígonos de Voronoi que generan las instalaciones de cada uno de los jugadores dentro de R. Nos referiremos a los npuntos colocados por White en Rcomo el conjunto Wy a los de Black como B, debiéndose cumplir que W∩B=∅. Además, supondremos que los puntos de un mismo jugador son distintos, lo cual es una premisa lógica, pues ambos jugadores buscan maximizar sus puntuaciones. En algunos resultados, además, se asumirá que ambos jugadores realizan las mejores jugadas a su alcance, la cual es una suposición coherente y que será necesaria para caracterizar completamente las estrategias ganadoras de esta variante. 34 juego de voronoi manhattan Se utilizará la notación V orP(p)para denotar al polígono de Voronoi del punto p∈P del diagrama de Voronoi de Pen R. El superíndice es importante, pues, en ocasiones, hablaremos de los polígonos de un mismo punto pero siendo distintos los conjuntos de puntos que conforman el diagrama en R. Por ejemplo, V orW(·)representa únicamente a los polígonos de los puntos de W(cuando todavía no están colocados los de Black), V orW∪{b}(·)son los polígonos del diagrama anterior añadiendo también el punto bde Black y V orW∪B(·)serían los polígonos que resultan una vez ambos jugadores han colocado sus puntos. Se pueden deducir fácilmente relaciones como, por ejemplo, V orW∪B(b)⊆V orW∪{b}(b), lo cual implica que Área(V orW∪B(b))≤Área(V orW∪{b}(b)). Esto último es claro pues, en una región R, un mismo polígono, cuando aumenta el número de puntos que conforman el diagrama, puede o mantenerse igual (los puntos añadido están lo suficientemente lejos de b) o verse reducido (los nuevos puntos no están lo suficientemente lejos y sus mediatrices redefinen su frontera), pero nunca aumentará de tamaño, porque los puntos que ya formaban su frontera, antes de añadir los nuevos, continúan. Esta relación será de utilidad más adelante. Figura 4.1: Ejemplo de un enfrentamiento (R, 3) (rectángulo Rde altura 1y base ρ con n= 3 puntos). En esta situación, se puede comprobar que el área de los polígonos blancos es mayor, luego White es el ganador. Observación 4.1.Como ya vimos en la subsección 2.2.2, a diferencia de la distancia euclídea, usando esta distancia podemos obtener polígonos con fronteras de medida positiva si la mediatriz correspondiente es degenerada. Esto significa que pueden darse enfrentamientos en los que ambos jugadores dominen estrictamente menos de 1/2·Área(R) (i.e., la suma del área que dominan ambos no es el área total Área(R)), quedando el área restante como una zona neutral. En el caso en el que dos puntos del mismo jugador formen una mediatriz degenerada, estas zonas neutrales se le asignarán a dicho jugador, de cara al recuento de puntuación. Podemos reemplazar esa 4. juego de voronoi manhattan a una ronda 35 frontera concreta por una mediatriz no degenerada. (a) (b) Figura 4.2: Un posible enfrentamiento para n= 2. En la primera figura, gana White. Si se cuentan, sin embargo, las zonas neutrales, gana Black. La mediatriz tipo III se ha sustituido por una vertical tipo I (podría haber sido también horizontal, no influye), sin que ello altere el enfrentamiento. Como vemos, es coherente e importante tener en cuenta las zonas neutrales entre puntos de un mismo jugador, como indica la Observación 4.1. A continuación, vamos a introducir una serie de conceptos básicos de los enfrentamientos que tienen lugar en el Juego de Voronoi. Definición 4.1. Sea un enfrentamiento (R, n)(área de juego Ry cada jugador dispone de ninstalaciones) y sean los conjuntos WyBdefinidos anteriormente. Se dice que B es un conjunto de puntos ganador para Black si este gana el enfrentamiento seleccionando B. Si acaba en empate, entonces Bes un conjunto de puntos de empate. Dado un conjunto W, un punto bde Black es un punto ganador si el área de V orW∩{b}(b)es mayor que 1/2n·Área(R). Un conjunto de puntos Wes invencible si no admite ningún conjunto de puntos ganador ByWserá un conjunto de puntos ganador para White si no existe ni un conjunto ganador ni un conjunto de empate para Black. Diremos que White o Black tienen una estrategia ganadora si pueden encontrar un conjunto de puntos ganador WoB, respectivamente. 4.1 Existencia de estrategia ganadora para Black El objetivo de esta sección es ver que, pese a la posibilidad de que existan mediatrices degeneradas utilizando esta distancia, Black tiene asegurada una estrategia 36 juego de voronoi manhattan ganadora si es capaz de colocar un punto ganador. Enunciaremos, a continuación, resultados que nos serán de utilidad para probar esto último. Proposición 4.1.Sean un rectángulo Ry un conjunto de puntos W⊂Rde White ya colocados. Entonces, para cada ε > 0y cada semipolígono Hdel conjunto W, Black puede colocar un punto btal que el área de V orW∩{b}(b)∩Hes, como poco, Área(H)−ε. Demostración. Recordemos que denotamos, como se introdujo al principio de la subsección 2.2.1, B(p, q)a la mediatriz (de la distancia d1) de los puntos p, q. Sean en R el conjunto de puntos Wde White y un punto w∈Wy consideremos, sin pérdida de generalidad, H⊂V orW(w)el semipolígono superior de w. Supongamos ahora que Black coloca en Run punto bligeramente por encima de w, esto es, si w= (x(w), y(w)), entonces b= (x(w), y(w) + δ), para δ > 0. En consecuencia, la mediatriz B(w, b)es de tipo II horizontal y el polígono V orW∪{b}(b)contiene ahora a todos los puntos de Hque se encontraban por encima de B(w, b). En virtud del punto tercero de la Proposición 2.1, el área de H\(V orW∪{b}(b)∩H)está acotada superiormente por el área del rectángulo generado por los brazos izquierdo y derecho de H(de longitudes biybd, respectivamente) y por la mitad superior del segmento wb, siendo la de dicho rectángulo (bibd)δ/2. En consecuencia, colocando ba una distancia δsuficientemente pequeña, la diferencia de área entre HyV orW∪{b}(b)∩Hes menor que cualquier ε > 0dado. □ Figura 4.3: Punto bde Black capturando casi la totalidad del área del semipolígono superior Hde un punto de White, donde V orW∪{b}(b)∩Haparece sombreado. En línea roja punteada parte del rectángulo mencionado del punto tercero de la Proposición 2.1. Se tiene, de hecho, por el siguiente resultado, que White debe colocar un conjunto de puntos Wbalanceado pues, de no ser así, Black tiene asegurada la victoria. Proposición 4.2.Sean Run rectángulo y Wun conjunto de puntos de White ya colocados en R. Si para algún semipolígono Hde W, se tiene que Área(H)= 1/2n·Área(R) 4. juego de voronoi manhattan a una ronda 37 (n=|W|), entonces Black tiene una estrategia ganadora. Demostración. Supongamos que existe un semipolígono de Wcon área distinta de 1/2n·Área(R), lo que equivale, por el Corolario 3.1, a que Wno es un conjunto de puntos balanceado. Entonces, existe un semipolígono Hde Wcon área mayor que 1/2n·Área(R) (supondremos, sin pérdida de generalidad, que es un semipolígono vertical). Consideremos los nsemipolígonos verticales de Wde mayor área H1, ..., Hn(sabemos ya que Hes alguno de estos Hi). Entonces existe δ > 0tal que Pn i=1 Área(Hi)= 1/2·Área(R) + δ. Por la Proposición 4.1, Black puede colocar, para cada Hi, un punto bitomando prácticamente toda su área salvo ε > 0. Escogiendo concretamente ε < δ/n, queda garantizado que existe un conjunto Bde npuntos b1, ..., bntales que n X i=1 (V orW∪B(bi)∩Hi)≥ n X i=1 (Área(Hi)−ε) = 1 2Área(R)+δ−nε > 1 2Área(R). En consecuencia, el conjunto B={b1, ..., bn}es un conjunto de puntos ganador, luego Black posee una estrategia ganadora. □ Lema 4.1.Sea Bun conjunto ganador de Black de forma que su puntuación es, a lo sumo, 1/2·Área(R). Entonces existe un conjunto de puntos B′de Black tal que su puntuación es mayor que 1/2·Área(R). Demostración. Supongamos un conjunto ganador para Black B. Entonces, la puntuación de Black supera a la de White. Ello implica que la suma de las puntuaciones no resulta Área(R) (pues la puntuación de Black era por hipótesis menor o igual que 1/2·Área(R)). Entonces existen mediatrices tipo III (entre puntos de distintos conjuntos) que generan zonas neutrales. Supongamos que estos dos puntos con una mediatriz tipo III son w= (x(w), y(w)) ∈Wyb= (x(b), y(b)) ∈B, luego |x(w)−x(b)|=|y(w)−y(b)|. Black podría evitar esta situación degenerada alterando ligeramente la posición de b. Moviéndolo a cualquier lado de la diagonal que pasaba por byw, la mediatriz tipo III pasa a ser no degenerada y Black puede ganar cualquiera de las dos zonas neutrales salvo, dependiendo del caso (a qué lado de la diagonal wb se desplace b), un ε > 0. Si las regiones neutrales eran de diferente área (algo que puede ocasionar el rectángulo Ro el resto de puntos de los jugadores) entonces, como puede optar por cuál de las zonas neutrales quedarse (según a qué lado de la diagonal wb desplace b), Black se asegura una ganancia de área. En otro caso, si las regiones neutrales eran iguales, entonces Black puede sufrir una 44 juego de voronoi manhattan Demostración. Sin pérdida de generalidad, supongamos que A1es el brazo inferior (el correspondiente al semipolígono inferior) de V orW(w),A2el brazo derecho y consideremos w= (0,0). Llamaremos Hal semipolígono derecho de V orW(w)y denotaremos como |Ai|a la longitud de los brazos Ai(ver Figura 4.7a). Consideremos que Black coloca un punto b= (δ, δ)dentro de V orW(w), para δ > 0. Con el objetivo de abarcar prácticamente la totalidad del semipolígono derecho de V orw(w), basta mover ba la derecha una distancia infinitesimal ε > 0. Omitiremos, sin embargo, para facilidad de la prueba, este término infinitesimal, que no afectará a los razonamientos que se presentan y, por ello, asumiremos que B(w, b)es vertical. Comparemos el área de V orW∪{b}(b)con el área de Hy veamos que existe un δ > 0de forma que el área de V orW∪{b}(b)es mayor que el área de H. Es más, como Área(H) = 1/2n·Área(R), entonces bserá un punto ganador y quedará probado el resultado. Ya vimos anteriormente un resultado (Proposición 4.2) que justifica que Htenga dicha área, pues Black tendría asegurada una estrategia ganadora de no ser así. Es claro que, una vez colocado b, todos los puntos de Hque se encontraban a la derecha de la mediatriz (vertical) B(b, w)pertenecen ahora a V orW∪{b}(b). Comparado entonces con H, la diferencia de área está acotada superiormente por δ|A1|+ 1/2δ2. Haciendo uso del Lema 4.2, como A3es interno (para así evitar la frontera de R, caso en el que el lema no estaba asegurado), entonces V orW∪{b}(b)∩Q1(w)gana un área, en el peor de los casos (A2podría ser brazo frontera, por lo que no habría ganancias hacia la derecha o, dependiendo del los puntos que formasen la frontera de H, la ganancia de área podría ser solo rectangular, como en dos de los casos del Lema 4.2) igual a δ(|A2|−δ). Se tiene entonces que el área de V orW∪{b}(b)sería, en el peor de los casos, 1/2n·Área(R)−(δ|A1|+1/2δ2)+δ(|A2|−δ), la cual es mayor que Área(H) si −(δ|A1|+1/2δ2)+δ(|A2|−δ)>0. Despejando δde la inecuación queda, haciendo uso de que δ > 0 −(δ|A1|+ 1/2δ2) + δ(|A2|−δ)>0 δ(|A2|−|A1|)−3/2δ2>0 δ(|A2|−|A1|)>3/2δ2 (|A2|−|A1|)>3/2δ 2/3(|A2|−|A1|)> δ En consecuencia, escogiendo δ < 2/3(|A2|−|A1|), se tiene que Área(V orW∪{b}(b)) >Área(H) 4. juego de voronoi manhattan a una ronda 45 y, por tanto, debido al valor de Área(H), bes un punto ganador de Black. □ Proposición 4.4.Sea un punto w∈Wtal que dos brazos opuestos de V orW(w)tienen diferente longitud y un tercer brazo es interno. Entonces, Black posee un punto ganador. Demostración. Sin pérdida de generalidad, consideremos que los brazos opuestos son el inferior y el superior, a los cuales llamaremos, respectivamente, A1yA3y supongamos que |A1|<|A3|, donde |Ai|denota, de nuevo, la longitud de Ai(ver Figura 4.7b). Supongamos que el brazo interno es el brazo derecho A2. Análogamente a la prueba de la Proposición 4.3 anterior, Black coloca un punto b= (δ, δ) y suponemos que B(w, b)es vertical (algo que, de nuevo, se consigue perturbando ε > 0el punto ba la derecha). Al igual que la prueba anterior, comparando con el semipolígono derecho de V orW(w)(que será denotado H), la diferencia de área entre HyV orW∪{b}(b)está acotada superiormente por δ|A1|+ 1/2δ2. Haciendo uso del Lema 4.2 y del hecho de que A2es interno, la ganancia de área, de forma similar a la prueba anterior, es, como poco, δ(|A3| − δ). Resolviendo la inecuación −(δ|A1|+ 1/2δ2) + δ(|A3|−δ)>0de forma análoga a la Proposición 4.3 previa, se deduce que, escogiendo δ < 2/3(|A3|−|A1|), el área de V orW∪{b}(b)es mayor que Área (H) y, en consecuencia, Black posee un punto ganador, pues Hposee un área de 1/2n·Área(R), como se argumentó en la prueba anterior. □ Ya tenemos los resultados necesarios para enunciar uno de los principales resultados de esta sección: una condición necesaria para que un conjunto de puntos de White sea invencible. Teorema 4.2. Sea un enfrentamiento (R, n), si Wes un conjunto de puntos invencible, entonces se cumplen las siguientes dos propiedades: 1. El área de cada semipolígono de Wes 1/2n·Área(R). 2. Los brazos de los polígonos que no son puentes (recordemos que, en la Definición 2.9, se definió un polígono puente como aquel que tiene brazos frontera opuestos) poseen igual longitud; los brazos frontera opuestos de los polígonos puente también son de igual longitud y, si |W|=n > 1, son los brazos de menor longitud. Demostración. Veamos la prueba de cada propiedad. 1. Supongamos que el conjunto de puntos Wde White es invencible, luego Black puede optar, en el mejor de los casos, a un empate. Ello implica que Black no 46 juego de voronoi manhattan (a) Caso de la prueba de la Porposición 4.3. El brazo inferior es más corto que el derecho y el superior es interno. En verde la ganancia que es segura (pues el brazo derecho podría ser frontera. En naranja δ|A1|+ 1/2δ2. (b) Caso de la prueba de la Porposición 4.4. El brazo inferior es más corto que el superior y el derecho es interno. En verde la ganancia segura, pues el brazo derecho es interno. En naranja δ|A1|+ 1/2δ2. Figura 4.7 tiene una estrategia ganadora, luego, haciendo uso de la Proposición 4.2, se tiene la propiedad 1. 2. Distinguimos dos casos según el número de puntos del enfrentamiento. Si n= 1, la propiedad 1. ya probada implica que los brazos opuestos del único polígono (que es puente) tienen la misma longitud, pues, de no ser así, los semipolígonos generados no tendrían igual área. Si n≥2, haciendo uso del Teorema 4.1, bastaría encontrar un punto ganador de Black si la propiedad 2. no se cumpliese Para un polígono con dos brazos vecinos internos, la Proposición 4.3 implica que todos sus brazos deben tener misma longitud, pues, de no ser así, Black poseería un punto ganador. Por otro lado, como |W|>1, todo polígono posee, al menos, un brazo interno. Entonces, la Proposición 4.4, implica que los brazos opuestos frontera de un polígono puente tienen misma longitud, pues de nuevo, en caso contrario, existiría un punto ganador para Black. Este hecho, sumado a que la Proposición 4.3 implica que el resto de los brazos, entonces, no son de menor longitud, prueba este segundo punto. Probadas ambas propiedades, concluye la demostración. □ Continuando con el análisis de los conjuntos invencibles para White, mostraremos, a continuación, que estos son conjuntos que conforman una cuadrícula. Previamente, 4. juego de voronoi manhattan a una ronda 47 enunciaremos y probaremos tres lemas que serán de utilidad. Lema 4.3.Sea Pun conjunto de npuntos en un rectángulo Rde altura 1 y base ρ y supongamos que Pcumple las dos propiedades del Teorema 4.2. Entonces Pes una cuadrícula. De forma más precisa, si ρ≥n, entonces Pforma una cuadrícula n×1. En caso contrario, Pforma una cuadrícula donde los polígonos de Voronoi son cuadrados. Demostración. La prueba la haremos por casos según sea mayor ρon. Caso 1: ρ≥n. Como Pcumple las dos propiedades del Teorema 4.2, entonces, por la primera propiedad, todos los semipolígonos de Ptienen área igual a1/2n·Área(R)= 1/2n·ρ≥1/2. Como la altura de cualquier semipolígono esta acotada superiormente por 1, entonces cada brazo derecho e izquierdo de los polígonos de Ptiene una longitud de al menos 1/2. Así, la propiedad segunda del teorema implica que los brazos inferior y superior de cada polígono tienen una longitud de 1/2(pues como mucho pueden sumar 1), lo cual implica que cada punto p∈Pestá colocado a altura 1/2respecto de la base de R. Por último, de nuevo por la primera propiedad, los puntos deben poseer todos la misma separación para tener el mismo área, por lo que la única opción es que Psea una cuadrícula n×1. Caso 2: ρ<n. Empezamos considerando el punto pcuyo polígono de Voronoi V or(p)contiene a la esquina superior izquierda de R. Recordemos que denotábamos a los cuartos de polígono de V or(p)como Ci(p), para i= 1,2,3,4. Es claro que C2(p)es un rectángulo, pues está acotado por la esquina superior izquierda de R. Además, se deduce que V or(p)no es un polígono puente, pues, de ser así, significaría que V or(p)contiene a la esquina inferior izquierda de R. En ese caso, como el segundo punto del Teorema 4.2 (aplicable pues n > 1al ser n > ρ ≥1) estipula que los brazos frontera opuestos de un polígono puente son los de menor longitud de entre todos los brazos del polígono, se tendría que la longitud de los brazos derecho e izquierdo sería, como poco, 1/2, al tener los brazos superior e inferior (brazos frontera del polígono puente) cada uno longitud 1/2(pues deben sumar 1), luego el semipolígono izquierdo de V or(p) tendría un área de, al menos, 1/2>1/2n·ρ= 1/2n·Área(R) y esto implicaría, como ya se vio en la Proposición 4.2, que Black tendría una estrategia ganadora. Nótese que no hemos considerado que V or(p)pueda contener a la esquina superior derecha porque entonces, por el razonamiento anterior, al cumplirse 48 juego de voronoi manhattan el segundo punto del Teorema 4.2, V or(p)debería ocupar todo Ry entonces no podría darse que n > 1. Descartado entonces que V or(p)pueda ser una celda puente, por la segunda propiedad del Teorema 4.2, todos los brazos de V or(p)tienen la misma longitud. La denotaremos d. Es directo, por la primera propiedad del anterior teorema y el punto segundo del Lema 3.1 ("Los cuartos de polígonos de V or(p)que son diagonalmente opuestos tienen la misma área."), que C2(p)yC4(p)tienen la misma área, luego ambos cuartos de polígono son cuadrados de lado d. La Figura 4.8a ilustra lo que sabemos hasta ahora. Consideremos, a continuación, la frontera derecha de C4(p)(que ya sabemos que es un cuadrado). Debe existir un punto q∈Ptal que la frontera derecha de C4(p)pertenezca a B(p, q)(por como se construyen los polígonos de Voronoi). Como el brazo derecho de V or(p)tiene una longitud dy la frontera derecha de C4(p)es vertical, entonces el punto qpertenece a O1(p)∪{y=y(p)}(donde y(p)denota, como en otras ocasiones, la ordenada de p) y, además, d1(p, q)=2d. Veamos la justificación de estas dos condiciones que cumple q. Como la frontera derecha de C4(p)es vertical, entonces B(p, q)debe ser vertical también. Si la mediatriz es vertical y queda a la derecha de p, entonces el punto debe pertenecer a O1(p)∪{y=y(p)}∪O8(p). Pero, si p∈O8(p), parte de la frontera derecha de C4(p)sería diagonal, y ya sabemos que esto no es así, luego q∈O1(p)∪ {y=y(p)}. Por otro lado, si qno estuviese a distancia 2dde p, entones la mediatriz no estaría a distancia dde p, lo que implicaría que la frontera derecha de C4(p)no estaría a distancia dde py, por tanto, el brazo derecha de V or(p)(cuya longitud es la distancia de la frontera derecha de C4(p)ap) no tendría longitud d. El segmento naranja de la Figura 4.8b representa las posibles ubicaciones de qque cumplen estas dos premisas. De lo anterior se deduce que el brazo izquierdo de V or(q)(que es la distancia a B(p, q)aq) también tiene longitud d. De nuevo, por la segunda propiedad del Teorema 4.2, el brazo superior de V or(q)también tiene longitud d. Esto localiza de manera única a q en {y=y(p)}. Es más, qes el único punto cuyo polígono comparte frontera con C1(p), pues, de no ser así, el brazo superior de qno tendría longitud d. En consecuencia, C1(p)también es un cuadrado. Por simetría, repitiendo el razonamiento anterior, debe existir un punto q′a distancia 2dde pque pertenezca a O6(p)∪{x=x(p)}y, análogamente, se deduce que C3(p)también es un cuadrado. Ello implica, por el punto segundo del Teorema 4.2, que todos los brazos de los polígonos de qyq′tienen longitud, al 4. juego de voronoi manhattan a una ronda 49 (a) La región roja representa el polígono V or(p). Los cuartos C2(p)yC4(p)son cuadrados. Por otro lado, las fronteras de C1(p)y C3(p)aparecen punteadas, pues aún no sabemos su forma. (b) El segmento naranja representa las posibles ubicaciones de q. En verde B(p, q). (c) Ya se conoce la forma de los cuartos de polígono 2ºy 4ºde qyq′y la situación es similar a la primera figura. (d) Una vez se conocen todos los polígonos frontera, se genera un rectángulo menor en el que se puede reiterar el proceso. En este ejemplo concreto, se acabará obteniendo una cuadrícula 5×3. Figura 4.8: Evolución de la prueba del caso 2 del Lema 4.3 menos, d. Es más, los cuartos de polígono C2(q)yC2(q′), como delimitan con la frontera de R, también son cuadrados y el Lema 3.1 y el hecho de que los brazos de V or(q)yV or(q′)midan, al menos, dimplican entonces que C4(q)yC4(q′) son también cuadrados (Figura 4.8c). 50 juego de voronoi manhattan Es claro que podemos usar, entonces, los mismos argumentos que antes usamos con V or(p)con estos dos nuevos polígonos de qyq′para ir localizando de forma iterativa las celdas frontera (recordemos, celdas que comparten parte de su frontera con parte de la de la región acotada en la que trabajamos, Ren este caso), que resultarán ser todos cuadrados. Se generaría entonces un rectángulo menor rodeado por estos polígonos frontera (ver Figura 4.8d) en el que, de nuevo, podríamos aplicar los razonamientos de esta prueba para llegar a la conclusión de que los puntos de Pforman una cuadrícula con polígonos de Voronoi que son cuadrados, lo que concluye la prueba de este segundo caso. Probados ambos casos, concluye la demostración. □ Lema 4.4.Sea Wen una región Rcuadrada tal que sus puntos forman una cuadrícula 2×2. Entonces Black tiene asegurado un punto ganador. Demostración. Como los puntos de Westán dispuestos en una cuadrícula 2×2y la región Res cuadrada, entonces podemos suponer que todos los brazos de todos los polígonos de Wposeen longitud d(se deduce, por tanto, que los lados de Rson de longitud 4d). Un punto bde Black será ganador si el área de su polígono es mayor que 1/2n·Área(R)= 1/8·16d2= 2d2. Situando el punto a distancia 3d/2de la frontera superior de Ry a distancia 3d/2 + δde la frontera izquierda, con δ > 0(para evitar una mediatriz degenerada con el punto superior izquierdo de W), se consigue que este punto sea ganador. El cálculo del área se puede hacer de forma directa, aunque también podemos usar el siguiente razonamiento. Se puede comprobar que, en el caso en el que bestuviese a distancia 3d/2de ambos lados de Rsuperior e izquierdo (ver Figura 4.9a), el área de V orW∪{b}(b)sería, añadiéndole la zona neutral que hace frontera con el lado superior de R, mayor que 2d2. En efecto, la suma de las áreas del rectángulo naranja, que es d/2·5d/2y los trapecios azules, ambos iguales, que suman un área de d2(d2/2 cada uno), es de 5d2/4 + d2= 2d2+d2/4>2d2. Al haber desplazado el punto b horizontalmente una cantidad δ > 0, de forma similar a la prueba del Lema 4.1, Black captura prácticamente la totalidad de la zona neutral de la que hablábamos. Sufre además ganancias de área con los puntos de Wde la mitad derecha de Ry una pérdida con el inferior izquierdo. Sin embargo, tomando δ > 0suficientemente pequeño, las pérdidas son mínimas y el área de V orW∪{b}(b)sería, prácticamente, 2d2+d2/4, lo cual lo convierte, holgadamente, en un punto ganador. □ 4. juego de voronoi manhattan a una ronda 51 (a) Celda para bcolocado a distancia 3d/2 de ambos lados de Rsuperior e izquierdo. El rectángulo naranja incluye una de las zonas neutrales para el cálculo del área, pues posteriormente, al perturbar b, esta será capturada por su celda. (b) Celda si colocamos ba distancias 3d/2 y3d/2 + δ. La zona neutral superior de la imagen primera ha sido capturada por el polígono de by las pérdidas de área ocasionadas por el desplazamiento δson ínfimas. Figura 4.9 Lema 4.5.Sea Wen una región rectangular Rde altura hy base a, con a≥n·h(se puede reescalar a dimensiones 1yρ:=a/h, pero por claridad de la prueba usaremos hya) tal que sus puntos forman una cuadrícula n×1, donde cada semipolígono de Wtiene un área de 1/2n·Área(R) (a fin de evitar la estrategia ganadora de Black), entonces Black no tiene ningún punto ganador ni tiene la posibilidad de empatar. Demostración. Salvo simetría, Black puede colocar un punto ben dos posiciones distintas respecto al punto correspondiente de Wmás cercano, al que denotaremos wb. Asumiremos, sin pérdida de generalidad, que wbestá a la izquierda de by, como poco, a la misma altura (nunca a menor altura que b). Denotaremos ∆x:=|x(wb)−x(b)| y∆y:=|y(wb)−y(b)|, donde hemos usado la notación p= (x(p), y(p)). Además llamaremos a′yh′a las longitudes de los brazos izquierdo y derecho y superior e inferior, respectivamente, de todas los polígonos de W. Se tiene entonces que a′= 1/2n·a yh′= 1/2·h. Usaremos en la prueba las medidas obtenidas en la Observación 2.4. La primera de las posiciones posibles (salvo simetría) es que ∆x>∆y. En tal caso, el área de V orW∪{b}(b)es, en el mejor de los casos (el polígono de bno está acotado por la frontera de R), 1/2n·Área(R)−∆y2. Para probar esta última afirmación, por claridad, nos ayudaremos de las áreas coloreadas en la Figura 4.10a. El área del polígono de bse compone de el área del semipolígono derecho de wb, quitando los 52 juego de voronoi manhattan rectángulos amarillo y azul oscuro y el triángulo verde oscuro, y sumándole las áreas de los rectángulos celeste, lila y el triángulo verde claro, formando parte, estas últimas tres figuras, del semipolígono izquierdo del otro punto blanco. Se puede comprobar que las áreas de las figuras son: Rectángulo amarillo: h′∆x+∆y 2. Rectángulo azul: h′∆x−∆y 2. Triángulo verde oscuro: (∆y)2 2. Rectángulo celeste: (h′+ ∆y)∆x−∆y 2(donde hemos usado que a′−∆x′+∆y 2= ∆x−∆y 2, donde ∆x′es la diferencia de abscisas entre by el otro punto blanco, pues ∆x′= 2a′−∆x). Rectángulo lila: (h′−∆y)∆x+∆y 2(donde hemos usado que a′−∆x′−∆y 2=∆x+∆y 2). Triángulo verde claro: (∆y)2 2. (a) Mejor caso para la primera de las posiciones posibles de la prueba del Lema 4.5. En rojo las mediatrices con b. Los lados izquierdos de los rectángulos celeste y lila coinciden con la frontera de los polígonos de wby el otro punto blanco. (b) Mejor caso para la segunda disposición del Lema 4.5. El polígono de bcaptura parte del área del semipolígono inferior de wb y parte de las celdas adyacentes a la de wb. Figura 4.10 El cómputo final queda Área(V orW∪{b}(b)) =1 2nÁrea(R)−h′∆x+ ∆y 2−h′∆x−∆y 2−∆y2 2+ (h′+ ∆y)∆x−∆y 2+ (h′−∆y)∆x+ ∆y 2+∆y2 2= 1/2n·Área(R)−∆y2 4. juego de voronoi manhattan a una ronda 53 como queríamos ver. Esta cantidad se maximiza cuando ∆y= 0, esto es, cuando bestá a la misma altura que los puntos de W. En efecto, al estar ba la misma altura entre dos puntos de W, las mediatrices correspondientes son tipo II verticales, y están a distancia ∆x/2(en el caso de wb) y (2a′−∆x)/2(en el caso del otro punto). Así, las áreas de los semipolígonos izquierdo y derecho que corresponden a bson h·∆x/2y h·(2a′−∆x)/2, que sumadas resultan ha′=h·1/2na = 1/2n·Área(R). Si ∆y= 0pero no existiese un punto de White a la derecha de b, entonces el semipolígono derecho correspondiente a bquedaría acotado por la frontera de R, lo que resultaría en una pérdida de área para V orW∪{b}(b). El otro caso posible, salvo simetría, es que ∆x≤∆y. Notemos que si ∆x= ∆ynos encontramos con una mediatriz tipo III. Por simplicidad, para poder tratarla con el resto de los casos, haremos el abuso de asignar la mitad de las zonas neutrales a by la otra mitad a wb, veremos que ello no afecta a la prueba, pues la mayor área se alcanzará en otra posición. Si colocamos bde forma que ∆x≤∆y, entonces el área del polígono de bes, en el mejor de los casos (su polígono no esta acotado por la frontera de R, como se muestra en la Figura 4.10b) 1/2n·Área(R)−∆y(w′−h′)−1/4(3(∆y)2+ (∆x)). Procedemos igual que antes, ayudándonos de la Figura 4.10b y obtenemos las áreas: Rectángulo verde: a′∆x+∆y 2. Rectángulo amarillo: a′∆y−∆x 2. Triángulo azul: (∆x)2 2. Triángulo celeste: (∆x−∆y)2 8. Rectángulo marrón: (h′−∆y)(∆x′′ +∆y 2−a′−∆x)=(h′−∆y)∆y−∆x 2. Triángulo lila: (∆x+∆y)2 8. Rectángulo naranja: (h′−∆y)(∆x′+∆y 2−a′+ ∆x) = (h′−∆y)∆y+∆x 2. Aquí ∆x′y∆x′′ representan las diferencias de abscisas entre by el punto blanco a la izquierda de wbyby el punto blanco a la derecha de wb, respectivamente. Se ha usado además que ∆x′= 2a′−∆xy que ∆x′′ = 2a′+ ∆x. Las áreas de las tres primeras figuras suman a′∆y+ (∆y)2/2, las de las dos siguientes suman 1/8(∆x)2+ 1/4∆x∆y−3/8(∆y)2+ 1/2h′∆y−1/2h′∆xy las de las dos últimas suman 1/8(∆x)2−1/4∆x∆y−3/8(∆y)2+ 1/2h′∆y+ 1/2h′∆x. Si sumamos las de estos dos últimos dos grupos, que son las figuras que no están en el polígono de wb, 60 juego de voronoi manhattan 5.2 Problemas y líneas de investigación abiertas Como hemos visto, existe una amplia variedad de estos problemas y ello lleva a que este sea un campo de la localización óptima de instalaciones aún con muchas incógnitas. En [5] y [8], por ejemplo, se plantean los escenarios en los que el área de juego Rno es simétrica o es más genérica que un cuadrilátero. Más aún, todavía siguen siendo problemas abiertos los Juegos de Voronoi con las distancias euclídea y Manhattan para el caso de turnos secuenciales, presumiblemente ambos de bastante mayor dificultad, como se indica en nuestro artículo principal [4]. En este último además, se plantean futuras líneas de investigación sobre temas ya estudiados en este trabajo. Concretamente, por ejemplo, sobre las configuraciones básicas balanceadas que vimos en el Capítulo 3. Se ha probado la unicidad de las configuraciones básicas de dos y tres puntos. ¿Existen otras configuraciones para más de tres puntos, además de las estudiadas?. Por ejemplo, para el caso de n= 7, solo conocemos configuraciones con zonas neutrales. En el caso de las configuraciones no básicas (las que eran unión de las básicas), ¿existen más formas de combinarlas, sin perder el balanceo, distintas a las que se han visto? Se apunta también en [4] al estudio de estas configuraciones balanceadas en escenarios más genéricos y con otras métricas. Más aún se pueden considerar variantes aún más generales donde las instalaciones de White y Black poseen pesos, llevándonos ello a trabajar con diagramas de Voronoi ponderados (diagramas de Voronoi en los que los puntos poseen pesos que, en consecuencia, afectan al cómputo final de la distancia). Para la variación del juego de maximizar vecinos, en [14] se plantean también algunas cuestiones, como por ejemplo la mejora de la cota (2n+ 2)/3ante- riormente presentada, la cual se conjetura que podría ajustarse a ⌈n/3⌉, así como la generalización también del problema mediante el uso de diagramas de Voronoi ponderados. En cuanto al problema del Juego del Aislamiento [19], se plantea el estudio de las posibles conexiones que pueda haber entre este y los Juegos de Voronoi. Bibliografía [1] Ahn, H., Cheng, S., Cheong, O., Golin, M., & Van Oostrum, R. (2004). Competitive facility location: the Voronoi game. Theoretical Computer Science, 310(1–3), 457–467. https://doi.org/10.1016/j.tcs.2003.09.004. [2] Bandyapadhyay, S., Banik, A., Das, S., & Sarkar, H. (2015). Voronoi game on graphs. Theoretical Computer Science, 562, 270–282. https://doi.org/10.1016/j.tcs.2014.10.00 [3] Bender, C. M., Bender, M. A., Demaine, E. D., & Fekete, S. P. (2003). What is the optimal shape of a city? Journal of Physics. A, Mathematical and General/Journal of Physics. A, Mathematical and General, 37(1), 147–159. https://doi.org/10.1088/0305-4470/37/1/010 [4] Byrne, T., Fekete, S. P., Kalcsics, J., & Kleist, L. (2022). Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game. Annals of Operation Research/Annals of Operations Research, 321(1–2), 79–101. https://doi.org/10.1007/s10479-022-04976-x. [5] Cheong, O., Har-Peled, S., Linial, N., & Matousek, J. (2004). The One-Round Voronoi game. Discrete and Computational Geometry/Discrete & Computational Geometry, 31(1), 125–138. https://doi.org/10.1007/s00454-003-2951-4. [6] Das, A. K., Das, S., Maheshwari, A., & Sarvottamananda, N. (2022). Voronoi games using geodesics. In Lecture notes in computer science (pp. 195–207). https://doi.org/10.1007/978-3-030-95018-7_16. [7] Das, A. K., Das, S., Maheshwari, A., & Sarvottamananda, N. (2023). Rectilinear Voronoi Games with a Simple Rectilinear Obstacle in Plane. In Lecture notes in computer science (pp. 89–100). https://doi.org/10.1007/978-3-031-25211-2_7. 62 juego de voronoi manhattan [8] Fekete, S. P., & Meijer, H. (2005). The one-round Voronoi game replayed. Computational Geometry, 30(2), 81–94. https://doi.org/10.1016/j.comgeo.2004.05.005. [9] Fekete, S. P., Mitchell, J. S. B., & Beurer, K. (2005). On the Continuous Fermat-Weber Problem. Operations Research, 53(1), 61–76. https://doi.org/10.1287/opre.1040.0137 [10] Kolen, A. (1981). Technical Note—Equivalence between the Direct Search Approach and the Cut Approach to the Rectilinear Distance Location Problem. Operations Research, 29(3), 616–620. https://doi.org/10.1287/opre.29.3.616 [11] Kusakari, Y., & Nishizeki, T. (1997). An algorithm for finding a region with the minimum total L 1 from prescribed terminals. In Lecture notes in computer science (pp. 324–333). https://doi.org/10.1007/3-540-63890-3_35 [12] Okabe, A., Boots, B., Sugihara, K., & Nok Chiu, S., (2000) Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. 2nd Edition, John Wiley & Sons, Chichester. [13] Preparata, F. P., & Shamos, M. I. (2012). Computational geometry: An Introduction. Springer Science & Business Media. [14] Rasheed, M. M., Hasan, M., & Rahman, M. S. (2009). Maximum neighbour voronoi games. In Lecture notes in computer science (pp. 93–104). https://doi.org/10.1007/978-3-642-00202-1_9. [15] Shafer, G. (2018). Pascal’s and Huygens’s game-theoretic foundations for probability. Sarton Lecture, School of Architecture and Engineering, University of Ghent. [16] Schwalbe, U., & Walker, P. (2001). Zermelo and the early history of game theory. Games and Economic Behavior, 34(1), 123–137. https://doi.org/10.1006/game.2000.0794 [17] Sun, X., Sun, Y., Xia, Z., & Zhang, J. (2020). The one-round multi-player discrete Voronoi game on grids and trees. Theoretical Computer Science, 838, 143–159. https://doi.org/10.1016/j.tcs.2020.06.028. [18] The Stanford Encyclopedia of Philosophy: https://plato.stanford.edu/entries/game-theory/ BIBLIOGRAFÍA 63 [19] Zhao, Y., Chen, W., & Teng, S. (2009). The isolation game: A game of distances. Theoretical Computer Science, 410(47–49), 4905–4919. https://doi.org/10.1016/j.tcs.2009.06.036.