Wiskunde en camerabewaking

Stel we willen een kamer beveiligen met videocamera’s. We veronderstellen dat we een videocamera in elke hoek van de kamer kunnen plaatsen, en de camera kan volledig rondom zich heen (dus 360°) kijken. De vraag luidt nu, “Hoeveel camera’s moeten we maximum plaatsen (en waar) om heel de kamer te bewaken?”.Dit probleem staat bekend als het ‘Chvatal’s bewaker probleem” (naar de man die als eerste het probleem onderzocht) of het “kunstgalerij probleem”.
Mona_Lisa,_by_Leonardo_da_Vinci,_from_C2RMF_retouched

Voor sommige kamers is het aantal nodige camera’s gelijk aan 1: In een vierkante kamer bijvoorbeeld. We plaatsen de camera in één van de vier hoeken en we kunnen de gehele kamer filmen. Ook voor een gelijkzijdige driehoek (of voor alle andere ‘gelijkvormige veelhoeken’) is het zo dat we de kamer met 1 camera kunnen filmen.
Voor iets moeilijkere kamers moeten we, om te weten hoeveel camera’s we maximum nodig hebben, enkel het aantal hoeken van onze kamer delen door 3. (als de uitkomst geen geheel getal is zoals dan ronden we de uitkomst af naar beneden, bijvoorbeeld voor een kamer met 16 hoeken zijn er 16/3=5,3333…5 camera’s nodig).Dit is niet zo moeilijk aan te tonen en volgt uit het volgende

Ik zal het meteen aantonen met een complexere figuur. Stel we hebben een ‘vreemde’ kamer die er als volgt uitziet (13 hoeken):
Afbeelding

Je merkt meteen dat er enkele ‘dode hoeken’ zijn, en dat de volledige kamer niet met één camera te observeren is (zoals gezegd mogen de camera’s enkel in hoeken geplaatst worden). Hier leg ik even uit hoe wiskundigen dit probleem te lijf gaan.
Allereerst trekken we strepen van hoek naar hoek, zodat we de gehele kamer ingedeeld hebben in driehoeken. Voor onze kamer kan dat het volgende opleveren (Er zijn meerdere mogelijkheden, zie verder).

Afbeelding

Nu kunnen we met drie verschillende kleuren elk hoekpunt inkleuren. We zorgen ervoor dat elke driehoek zowel een groen, geel en rood hoekpunt hebben.

Afbeelding

Nu hoeven we enkel een kleur te kiezen (bijvoorbeeld rood) en als we op die hoekpunten een camera plaatsen filmen we de gehele kamer. In ons geval (met de rode hoeken) zijn dat dus 4 camera’s. Dit wisten we eigenlijk al want de kamer heeft 13 hoeken en dus 13/3 = 4.33333 en afgerond naar beneden is dat dus 4. maar nu weten we dus ook waar we de camera’s moeten plaatsen.

Nu had ik gezegd dat het aantal hoeken gedeeld door 3, het maximum aantal camera’s weergeeft. Het is dus soms ook mogelijk om het met minder camera’s op te lossen (en dus goedkoper). zoals gezegd kan je de kamer op verschillende manieren in driehoeken verdelen. Hieronder heb ik het op de volgende manier gedaan…

Afbeelding
…weer elk hoekpunt zo inkleuren dat elke driehoek exact één rode, gele en groene hoek hebben…

Afbeelding
…Als we nu enkel de rode hoeken nemen krijgen we het volgende:
Afbeelding
Het is dus ook met 2 camera’s op te lossen! Deze methode wordt overal gebruikt waar camera bewaking nodig is, zoals bijvoorbeeld kunstgalerijen, banken, ……  Het is namelijk altijd voordelig om de kosten zo laag mogelijk te houden!

DAAROM WIKSUNDE

Giedts T.

Advertisements

1 Comment

Filed under Wiskunde vs. Misdaad, wiskundige carrière

One response to “Wiskunde en camerabewaking

  1. Pingback: London tube en GPS | waaromwiskunde

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s