Aquest problema de geometria computacional, enganyosament senzill, va ser proposat inicialment al 1973 per el geòmetre i topòleg Victor Klee.
Suponguem que tenint el plà de la planta d'una galeria es desitja saber quants guàrdies es necesiten colocar per a que tot punt de la galeria estiga continuament vigilat. De manera equivalent es poden imaginar llums en compter de guàrdies i així requerim ilimunació completa.
El problema es pot definir formalment com:
-Donat un polígon simple de n costats, determinar el mínim nombre de vèrtex des de els que es possible vore tots els punts interiors del polígon.
Per a un polígon simple amb n costats, (n/3) guardies son a vegades necessaris i sempre suficients per a vigilar un polígon. Aquests guardies poden sempre colocarse als vèrtex del polígon.
Faltes a corregir:
ResponderEliminargeòmetre
Suponguem que tenint el plà
desitja
necesiten colocar per a que
en compter de guàrdies i així requerim ilimunació completa.
el mínim nombre de vèrtex des de els que es
**Aquesta frase no l'has entés: **
Per a un polígon simple amb n costats, (n/3) guardies son a vegades necessaris i sempre suficients per a vigilar un polígon. Aquests guardies poden sempre colocarse als vèrtex del polígon.