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.

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  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  in  is zichtbaar vanuit een ander punt  in  als het lijnstuk  een deelverzameling is van . De verzameling van alle punten die zichtbaar zijn vanuit , noemen we . Dit is steeds een stervormige veelhoek.

Stel er zijn  suppoosten. De posities van de suppoosten vormen een verzameling  van punten in  die de  gehele veelhoek  moeten bestrijken. Elk punt in  moet zichtbaar zijn vanuit minstens een van de punten in ; dit wil zeggen dat de vereniging van , gelijk is aan .

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

Met  wordt de maximumwaarde aangeduid van  voor alle veeltermen met  hoeken.

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

Stelling van Chvátal
Chvátal kwam in 1975 met een bewijs van de stelling, dat  suppoosten altijd voldoende zijn, en soms nodig, om een veelhoek met  hoekpunten te bewaken. ( is de entier van ). 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  hoeken is dit aantal punten steeds .

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  van  te vinden die  volledig "overdekt" ("kan zien"). Maar  is hier een oneindig grote verzameling van punten. Om de technieken die voor het set cover-probleem zijn ontwikkeld te kunnen gebruiken, kan men  discretiseren. Het discrete probleem is dan een verzamelingoverdekking door  te vinden van een eindige verzameling van punten uit .

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  die de gekozen punten van  kan zien; maar het is mogelijk dat er nog gebieden in  zijn die niet zichtbaar zijn vanuit . De methode is met andere woorden iteratief. Als er een gebied overblijft dat niet zichtbaar is vanuit , 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  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

 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  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  ziet een punt  dat buiten de veelhoek ligt wanneer het lijnstuk  de rand van de veelhoek niet snijdt (raken mag wel). Hiervoor is  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  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 link 
Wiskunde en camerabewaking.

Wiskundig vraagstuk
Meetkunde
NP-moeilijk probleem