Κοίλο πολύγωνο

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

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

Παραπομπές

Εξωτερικοί σύνδεσμοι 
 

Πολύγωνα