Kunstgalerijprobleem

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
Vier bewakers kunnen deze galerij volledig bewaken. De blauwe, rode en groene gebieden worden door een bewaker bestreken, de andere door minstens twee.
Voor deze veelhoek met zes hoekpunten zijn twee bewakers nodig en voldoende.

Het museumprobleem of kunstgalerijprobleem (Engels: art gallery problem) is een wiskundig probleem uit de computationele meetkunde: hoeveel bewakers 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 bewaker liggen. We veronderstellen dat de bewakers stationair zijn en een gezichtsveld van 360° hebben.

Dit probleem en allerlei variaties erop zijn uitgebreid bestudeerd en in 1987 wijdde Joseph O'Rourke er zelfs een volledige monografie aan.[1] 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.[2]

Probleemomschrijving[bewerken | brontekst bewerken]

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 wanneer het lijnstuk [pq] een deelverzameling is van P. De verzameling van alle punten die zichtbaar zijn vanuit q noemen we Vis(q). Dit is steeds een stervormige veelhoek.

Stel er zijn m bewakers. De posities van de bewakers zijn een verzameling G = {g1, g2... gm} 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 Vis(gi), i=1, 2, ... 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 bewakers dat een willekeurige galerij met n hoeken kan bewaken.

Stelling van Chvátal[bewerken | brontekst bewerken]

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

Bewijs van Fisk[bewerken | brontekst bewerken]

Fisk[4] 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. Vermits 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 ≤ n/3 .

Dit is een voorbeeld van een veelhoek en een mogelijke triangulatie ervan, voorzien van een 3-kleuring. Er zijn 11 hoekpunten, waarvan er 4 rood, 4 groen en 3 blauw zijn gekleurd. De veelhoek kan dus vanuit 3 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[bewerken | brontekst bewerken]

Er zijn verschillende algoritmes bedacht om voor een bepaalde galerij het minimaal aantal benodigde bewakers 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 Vis(gi) te vinden van een eindige verzameling van punten uit P.

Voor de situatie waarin de bewakers enkel 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.[5]

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

Varianten[bewerken | brontekst bewerken]

Er bestaan vele varianten van het origineel probleem. In sommige versies zijn de bewakers beperkt tot de rand van de veelhoek, of mogen ze enkel 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 wanneer de bewakers op elk punt in de veelhoek mogen staan.

Wanneer alle zijden van de veelhoek rechte hoeken met elkaar vormen, spreekt men van een orthogonale veelhoek. Voor zulke veelhoeken is bewezen dat bewakers altijd voldoende zijn.

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

Verwante problemen[bewerken | brontekst bewerken]

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 een nodig en voldoende aantal.[7]. Er zijn dus meer bewakers nodig om de buitenzijde van een willekeurige veelhoek te bewaken dan de binnenzijde. Voor een orthogonale veelhoek echter zijn bewakers nodig en voldoende; dit verschilt slechts weinig van de 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 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 links[bewerken | brontekst bewerken]