Kunstgalerijprobleem

Het museumprobleem of kunstgalerijprobleem (Engels: art gallery problem) is een wiskundig probleem uit de computationele meetkunde: hoeveel suppoosten zijn er minimaal nodig om een kunstgalerij te bewaken, waarvan de plattegrond een eenvoudige veelhoek is? Elk punt in de galerij moet dus in het gezichtsveld van minstens een suppoost liggen. We veronderstellen dat de suppoosten stationair zijn en een gezichtsveld van 360° hebben.

Vier suppoosten kunnen deze galerij volledig bewaken. De blauwe, rode en groene gebieden worden door één suppoost bestreken, de andere door minstens twee.

Voor deze veelhoek met zes hoekpunten zijn twee suppoosten nodig en voldoende.

Dit probleem en allerlei variaties erop zijn uitgebreid bestudeerd en in 1987 wijdde Joseph O'Rourke er zelfs een volledige monografie aan. Victor Klee formuleerde het probleem in de rand van een wetenschappelijk congres in 1973 als antwoord op een vraag van Vasek Chvátal voor een interessant meetkundig probleem.

Probleemomschrijving

De galerij wordt voorgesteld als een gesloten deelverzameling $P$ van het vlak waarvan de rand een eenvoudige veelhoek is, dus zonder gaten of zijden die elkaar snijden. Anders gezegd: de rand is een gesloten jordan-kromme die bestaat uit rechte lijnstukken.

Een punt $p$ in $P$ is zichtbaar vanuit een ander punt $q$ in $P$ als het lijnstuk $[pq]$ een deelverzameling is van $P$. De verzameling van alle punten die zichtbaar zijn vanuit $q$, noemen we $\mathrm {Vis} (q)$. Dit is steeds een stervormige veelhoek.

Stel er zijn $m$ suppoosten. De posities van de suppoosten vormen een verzameling $G=\{g_{1},g_{2},\ldots ,g_{m}\}$ van punten in $P$ die de gehele veelhoek $P$ moeten bestrijken. Elk punt in $P$ moet zichtbaar zijn vanuit minstens een van de punten in $G$; dit wil zeggen dat de vereniging van $\mathrm {Vis} (g_{i}),\,i=1,2,\ldots ,m$, gelijk is aan $P$.

Voor een gegeven veelhoek $P$ is $G(P)$ het minimaal aantal punten in $P$ dat $P$ geheel bestrijkt; het is de kleinste cardinaliteit van alle mogelijke verzamelingen $G$.

Met $g(n)$ wordt de maximumwaarde aangeduid van $G(P)$ voor alle veeltermen met $n$ hoeken.

Het probleem dat Klee oorspronkelijk formuleerde, kwam neer op het bepalen van $g(n)$. Dit is dus het kleinste aantal suppoosten die een willekeurige galerij met $n$ hoeken kunnen bewaken.

Stelling van Chvátal

Chvátal kwam in 1975 met een bewijs van de stelling, dat $\left\lfloor n/3\right\rfloor$ suppoosten altijd voldoende zijn, en soms nodig, om een veelhoek met $x$ hoekpunten te bewaken. ($\left\lfloor x\right\rfloor$ is de entier van $x$). Dit is een bovengrens voor het minimaal aantal suppoosten. De galerij in het voorbeeld hiernaast heeft 42 hoeken maar toch zijn slechts vier suppoosten of bewakingscamera's nodig om de hele galerij te surveilleren.

Bewijs van Fisk

Fisk publiceerde in 1978 een eenvoudig bewijs van deze voldoende voorwaarde. Het beslaat slechts enkele regels en is gebaseerd op een triangulatie van de veelhoek in driehoeken, die de hoekpunten van de veelhoek als hoekpunt hebben. Uit de grafentheorie is bekend dat een triangulatiegraaf een knopenkleuring heeft met drie kleuren. De hoekpunten van elke driehoek hebben een verschillende kleur. Aangezien een driehoek convex is, kan hij vanuit een hoekpunt volledig bewaakt worden. En daar elk punt van de veelhoek behoort tot een driehoek, kan de veelhoek volledig bewaakt worden vanuit de hoekpunten met gelijke kleur. Kies nu uit de drie verzamelingen van hoekpunten met gelijke kleur diegene met de minste elementen; voor een veelhoek met $n$ hoeken is dit aantal punten steeds $\leq n/3$.

• 
  Een veelhoek met 11 hoekpunten
• 
  Een triangulatie van de veelhoek

Dit is een voorbeeld van een veelhoek en een mogelijke triangulatie ervan, voorzien van een driekleuring. Er zijn elf hoekpunten, waarvan er vier rood, vier groen en vier blauw zijn gekleurd. De veelhoek kan dus vanuit drie punten (de blauwe) volledig overzien worden, zoals de stelling van Chvátal zegt. Maar dit is niet het minimumaantal punten; er is een andere triangulatie mogelijk waarbij slechts twee punten dezelfde kleur hebben.

Optimale oplossingen

Er zijn verschillende algoritmes bedacht om voor een bepaalde galerij het minimaal aantal benodigde suppoosten te bepalen en de plaats die ze moeten innemen. Het is bekend dat dit een NP-moeilijk optimaliseringsprobleem is.

Een benadering die vaak wordt gebruikt, is om het kunstgalerijprobleem te beschouwen als een variant van het set cover-probleem. Het is inderdaad de bedoeling om een deelverzameling $G$ van $P$ te vinden die $P$ volledig "overdekt" ("kan zien"). Maar $P$ is hier een oneindig grote verzameling van punten. Om de technieken die voor het set cover-probleem zijn ontwikkeld te kunnen gebruiken, kan men $P$ discretiseren. Het discrete probleem is dan een verzamelingoverdekking door $\mathrm {Vis} (g_{i})$ te vinden van een eindige verzameling van punten uit $P$.

Voor de situatie waarin de suppoosten alleen in de hoekpunten mogen plaatsnemen, kan men de oplossing bijvoorbeeld zoeken met behulp van 0-1-geheeltallige programmering. De oplossing is een minimale verzameling hoekpunten $G$ die de gekozen punten van $P$ kan zien; maar het is mogelijk dat er nog gebieden in $P$ zijn die niet zichtbaar zijn vanuit $G$. De methode is met andere woorden iteratief. Als er een gebied overblijft dat niet zichtbaar is vanuit $G$, breidt men de verzameling discrete punten uit met een of meer punten uit dit gebied, en lost het nieuwe set cover-probleem op.

Men kan bewijzen dat dit algoritme in een eindig aantal stappen convergeert naar een oplossing, die de optimale oplossing is. Het aantal niet-zichtbare gebieden is namelijk eindig, en vermindert tijdens de iteraties. Merk ook op dat in elke iteratiestap een NP-moeilijk set cover-probleem moet opgelost worden. Het is daarom van belang om een goede discretisatie-strategie te bepalen, waarmee het aantal iteraties zo klein mogelijk wordt gehouden.

Andere benaderingswijzen doorzoeken de triangulaties van de veelhoek, of de partities van de veelhoek in convexe veelhoeken.

Varianten

Er bestaan vele varianten van het origineel probleem. In sommige versies zijn de suppoosten beperkt tot de rand van de veelhoek, of mogen ze alleen in een hoekpunt van de veelhoek staan. In het bewijs van Fisk zijn ze beperkt tot de hoekpunten. Het resultaat van Chvátals en Fisk is ook geldig als de suppoosten op elk punt in de veelhoek mogen staan.

Als alle zijden van de veelhoek rechte hoeken met elkaar vormen, spreekt men van een orthogonale veelhoek. Voor zulke veelhoeken is bewezen dat $\left\lfloor n/4\right\rfloor$ suppoosten altijd voldoende zijn.

Er zijn ook afwijkende configuraties bestudeerd, zoals veelhoeken met gaten, of galerijen waarvan de zijden geen rechte lijnstukken zijn, of situaties waarin de suppoosten een zekere mate van bewegingsvrijheid hebben. Ook de uitbreiding naar drie dimensies is mogelijk.

Verwante problemen

Om de buitenkant van dit "fort" met 24 hoeken te bewaken zijn zeven bewakers nodig

• Het "fortprobleem" (fort problem) vraagt: hoeveel bewakers zijn er minimaal nodig om de buitenkant te bewaken van een fort (dit is opnieuw een veelhoek met $n$ zijden)? De buitenkant is het complement van de veelhoek en strekt zich dus oneindig ver uit. De bewakers moeten op hoekpunten van de veelhoek staan. Een bewaker $z$ ziet een punt $x$ dat buiten de veelhoek ligt wanneer het lijnstuk $[zx]$ de rand van de veelhoek niet snijdt (raken mag wel). Hiervoor is $\left\lceil n/2\right\rceil$ een nodig en voldoende aantal. Er zijn dus meer bewakers nodig om de buitenzijde van een willekeurige veelhoek te bewaken dan de binnenzijde. Voor een orthogonale veelhoek echter zijn $\left\lceil n/4\right\rceil +1$ bewakers nodig en voldoende; dit verschilt slechts weinig van de $\left\lfloor n/4\right\rfloor$ die volstaan voor het bewaken van de binnenzijde. En indien men toelaat dat de bewakers op een willekeurig punt in het vlak buiten de veelhoek staan, zijn $\left\lceil n/3\right\rceil$ bewakers nodig en voldoende.

• Het "probleem van de gevangenisbinnenplaats" (prison yard problem): op de muur rond een binnenplaats staan bewakers die tegelijk de binnenplaats en de omgeving moeten bewaken. Hoeveel bewakers, geplaatst op de hoekpunten van een veelhoek, zijn dan minimaal nodig om zowel de binnen- als de buitenzijde van de veelhoek te bewaken?

Externe link

• Wiskunde en camerabewaking.

Bronnen, noten en/of referenties