Πρόβλημα γκαλερί τέχνης. Πόσα άτομα χρειάζονται για ασφάλεια σε μια γκαλερί;

Φανταστείτε ότι είστε ο επικεφαλής της ασφάλειας σε μια μεγάλη γκαλερί τέχνης. Υπάρχουν πολλοί πολύτιμοι πίνακες που καλύπτουν τους τοίχους της γκαλερί. Καθήκον σας είναι να τους προστατεύσετε. 

Η γκαλερί αποτελείται από δωμάτια διαφορετικών σχημάτων και μεγεθών. Ωστόσο, δεν έχετε αρκετά χρήματα για να έχετε έναν συνοδό υπεύθυνο για κάθε πίνακα. Σε αυτήν την περίπτωση, πώς μπορείτε να διασφαλίσετε την ασφάλεια όλων των εικόνων στη γκαλερί χρησιμοποιώντας τον ελάχιστο αριθμό φυλάκων; 

Αυτή η ερώτηση είναι ένα από τα σημαντικά ερωτήματα στην υπολογιστική γεωμετρία. Η υπολογιστική γεωμετρία είναι ένας κλάδος της επιστήμης των υπολογιστών που είναι αφιερωμένος στη μελέτη αλγορίθμων που μπορούν να εκφραστούν γεωμετρικά. Προβλήματα στην υπολογιστική γεωμετρία έχουν ενσωματωθεί στην επιστήμη των υπολογιστών μέσω μαθηματικής απεικόνισης και μοντελοποίησης.

Τέτοια προβλήματα γεωμετρίας εμφανίζονται φυσικά και στον προγραμματισμό βιντεοπαιχνιδιών, όπου είναι συχνά απαραίτητο να εκτελούνται υπολογισμοί με βάση έναν εικονικό κόσμο για να δημιουργηθεί μια ρεαλιστική εμπειρία του χρήστη.

Το πρόβλημα τέθηκε από τον Victor Klee το 1973 και αποδείχθηκε από τον Vaclav Chvátal το 1975. Ωστόσο, καθώς αυτή η απόδειξη ήταν αρκετά περίπλοκη, μια δεύτερη και συντομότερη απόδειξη του προβλήματος πραγματοποιήθηκε από τον Steve Fisk το 1978. 

Με γεωμετρικούς όρους, το πρόβλημα είναι το εξής: δεδομένου ενός πολυγώνου με $n$-κορυφές, ποιος είναι ο ελάχιστος αριθμός φρουρών για να επιτηρείς κάθε σημείο μέσα στο πολύγωνο;