Vigilant polígons

El llibre de Clara Grima Hasta el infinito y más allá conté un capítol titulat  ¿Por qué no hay un poli en cada sala? on es presenta el problema del que parlarem ara. També va ser motiu d'una entrada a un dels seus blogs: Cuántos nos están vigilando. No millorarem el que ella ha escrit, però si que intentarem plantejar-ho com una possible seqüència didàctica per treballar el problema a l'aula. Som-hi doncs!

Imaginem que tenim una sala, per exemple d'un museu, on hem de situar una persona vigilant, tenint en compte que pot girar sobre sí mateix però no desplaçar-se. Si volem podem imaginar-nos un vigilant-mussol capaç de girar el seu cap 360º (imaginar-se la nena de l'exorcista girant el cap és més desagradable) o una càmera que gira sobre un eix.

Si tenim una sala en forma de quadrilàter, com el de l'exemple sota, és indiferent on col·loquem el vigilant. Sempre tindrà tota la sala en el seu camp d'observació, fins i tot posant-se a una cantonada.

Una sala una mica més complexa pot ser més exigent a l'hora de triar el lloc del vigilant, ja que no des de qualsevol lloc la visió és completa.

Algunes sales necessitaran, de totes totes, més d'un vigilant, encara que hi hagi zones sobrevigilades.

El problema tracta justament d'això: donada una sala poligonal qualsevol mirar quina és la quantitat de vigilants mínima que calen, on s'han de posar... i fins i tot treballarem un algoritme que ens ajuda a resoldre totes dues qüestions.

Vols estudiar el problema?

Què veu el vigilant?

Aquesta és una de les primeres qüestions importants de plantejar a l'aula: determinar geomètricament que que queda en el camp de visió d'un vigilant. No és una qüestió tan senzilla com pot semblar a primera vista perquè hem de determinar les zones que queden tapades per parets i observar quines són línies rectes que ens delimiten la regió que podem veure. Això implica aprendre a "canviar el punt de vista". És una bona activitat per fer en petit grup i convidar a l'argumentació.

Segons els polígons que presentem i el lloc on col·loquem el vigilant pot ser més fàcil o difícil delimitar el camp de visió. Una forma de simplificar-ho és posant una condició: que els vigilants es col·loquin obligatòriament en els vèrtexs dels polígons, així dos costats ja ens marcaran dues fronteres.

Primeres casos i primeres conclusions

En tots aquests polígons amb un sol vigilant n'hi ha prou per controlar tota la sala. A més, és indiferent on s'hi posa.

Què tenen en comú? No és la quantitat de costats, ja que tenim un triangle, un quadrilàter, un pentàgon i un decàgon. El que tenen en comú és que són convexos.

En canvi en aquests polígons cal tan sols un vigilant, però només si el col·loquem en algun lloc estratègic. Si no ho fem podem necessitar més.

Què tenen en comú? Que són còncaus.

Per tant tenim un primera conclusió: a les sales poligonals convexes passem sempre a un vigilant, independentment de la seva posició. A les còncaves la cosa no és tan senzilla.

Ataquem els polígons còncaus

Es pot proposar a classe una discussió sobre mètodes per trobar posicions òptimes pels vigilants. Una estratègia de possible aparició és la següent: si al polígons convexos un vigilant "ho veu tot" podem descompondre el polígon còncau en d'altres convexos. Si són els mínims millor. Després a cada polígon hi col·locarem un vigilant.

Podem millorar la solució? La resposta, en aquest cas, és que sí. Una pregunta possible és la següent: poden reunir-se els vigilants, ni que sigui de dos en dos, per fer petar la xerrada sense perdre de vista la seva zona assignada? En el nostre cas es poden localitzar dos "punts de trobada".

Aquests punts que hem marcat ni són els únics ni tenen per què ser-hi als vèrtexs. Una nova possible proposta de discussió és definir on poden ser aquests llocs.

El pas següent és obvi: per què no fem d'aquests punts de trobada "llocs de vigilància"? D'aquesta forma amb tan sols dos vigilants podem controlar tota la sala poligonal.

 Els nostres dos vigilants encara es poden parlar per senyes. O millor buscar una zona pròxima de conversa. Però, en tot cas, aquesta sala no la podrem vigilar amb menys de dos vigilants.

Una mena d'algoritme per trobar llocs de vigilància idonis

A partir de la demostració d'Steve Fisk, apareguda al 1978, i que Clara Grima ens explica magníficament en el seu llibre, podem descriure un mètode per localitzar punts de vigilància com els que hem descrit i minimitzar la quantitat de vigilants necessaris. És molt fàcil de seguir i a primària es pot aplicar sense dificultats. Es basa en dues idees:

• tots els polígons es poden triangular
• podem pintar els vèrtexs d'una xarxa triangular amb només tres colors de forma que no es repeteixin colors en un sol triangle.

En la següent animació podem observar el mètode.

Bé... amb cinc vigilants tenim prou. Però, no en sobra cap? Potser haurem de revisar les seves zones de vigilància per valorar-ho. Fins ara el procediment era clarament algorítmic; ara no ho serà tant.

En aquesta animació podem veure les regions d'observació de cada vigilant.

Si ens hi fixem amb atenció hi ha zones sobrevigilades que possibiliten descartar un vigilant.

Però hem d'estar atents a les zones que poden quedar sense vigilància. Si observes combinacions com 2-3-4 o 3-4-5 veuràs que queden zones molt petites sense vigilància.

Per tant, distribuïts així, ens caldran quatre d'aquests vigilants com a mínim. Podem eliminar el vigilant 1 o el vigilant 2.

Canviar el vigilant que ara tesà alvèrtex 5 de lloc ens dóna, però, la possibilitat de reduir encara un altre vigilant i passar amb tres només.

Dues solucions: 1-3-5 i 2-3-5

Com es pot observar cada polígon particular dóna la seva feina, però aplicant uns criteris geomètrics generals no costa tant arribar a una solució òptima.

Estudiar el "mínim-màxim"

Del mètode explicat anteriorment (basat en la triangulació i pintat per situar els vigilants i sense fer la depuració final) podem proposar encara una investigació més a l'aula: quina és la quantitat màxima suficient per vigilar una sala poligonal de n costats. Potser cal explicar què vol dir màxima suficient. La quantitat màxima per vigilar l'assenya el seu aforament amb tot de vigilants ben anxovats els uns contra els altres i sense deixar espai per a cap visitant. Té ben poc interés. Però ja hem vist que a la sala de l'apartat anterior eren suficients 5 vigilants per controlar-la tota. Després hem aconseguit reduir-ho a tres. Això ha estat gràcies a les característiques de la sala. Sense tenir-les en compte 5 vigilants era la quantitat màxima suficient. També podríem dir que és el mínim-màxim.

Aquest mínim-màxim de vigilants sembla dependre de la triangulació. La quantitat de triangles obtinguts en un polígon donat depèn, a la seva vegada, de la quantitat de costats. Així, no sembla antinatural pensar que el mínim-màxim depèn del nombre de costats. Aquesta és la següent investigació que es pot proposar a classe.

• primer fem aplicar el mètode de Fisk (triangular-pintar-comptar-triar) a polígons de 3, 4, 5... 11,12...costats i fem una taula amb la quantitat de vigilants obtinguts en cada cas.
• a continuació busquem la pauta.

Es tracta de repartir entre la classe polígons amb diferents quantitats de costats (preferiblement còncaus a partir de 3), fins el nombre que vulguem. Convé repetir polígons amb quantitats de costats iguals perquè no sempre s'obté el mateix resultat. Per triar la dada a anotar a la taula final hem de tenir en compte el següent:

•  mirar de tots els casos ben resolts quines han estat les quantitats més baixes de vigilants.
• entre aquestes triar la més alta de totes.

 Així, per exemple, amb aquests hexàgons diferents les més baixes són 1, 1 i 2. La que cal anotar és 2.

També triangulacions diferents d'un mateix polígon poden donar una quantitat mínima de vigilants diferent. Les més baixes d'aquest hexàgon són 1 i 2 i ens quedarem amb el 2.

 Amb totes les dades recollides podrem construir una taula com la següent:

Costats	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	...
Vigilants	1	1	1	2	2	2	3	3	3	4	4	4	5	5	5	6	6	6	7	...

No és difícil descobrir la fórmula: el mínim-màxim de vigilants l'obtenim agafant la part entera de la divisió del número de costats entre tres.

Reduir aquest mínim-màxim dependrà ja de les característiques del polígon. Sempre estarem entre 1 i el nombre que hem calculat a partir de n/3.

Final

Aquest problema es coneix amb el nom usual de problema de la galeria d'art i podem trobar múltiples referències a internet, entre elles a la pròpia viquipèdia.  També localitzarem problemes semblants relatius a la il·luminació d'interiors, exteriors, amb miralls... El problema va ser plantejat per Victor Klee al 1973 i resolt i demostrat poc després per Vàclav Chvàtal. Més tard Steve Fisk va simplificar, com hem vist, la demostració al 1978.

Jo l'he conegut, com ja s'ha dit, pel llibre de Clara Grima (gràcies per ser tan clara).

I, per acabar, un problema que encara no està resolt:

Si permetem que cada guàrdia pugui patrullar per una de les parets del museu, de manera que vigili tots els punts que són visibles des d'algun punt d'aquesta paret, quants guàrdies es necessiten per fer la vigilància en una sala poligonal de n costats?