Γεωμετρικό γράφημα καλείται ένα σύνολο σημείων V στο επίπεδο μαζί με ένα σύνολο ευθυγράμμων τμημάτων (ακμών) E που έχουν τα άκρα τους στο V, και εύκολα συσχετίζεται με το "αφηρημένο" γράφημα G(V,E). Μελετώντας το πάχος του, δηλαδή τη διαμέριση των ακμών του σε υποσύνολα ελεύθερα διασταυρώσεων (ένα NP-δύσκολο πρόβλημα βελτιστοποίησης), προκύπτει και το πρόβλημα της ύπαρξης τριγωνοποίησης ως ένα ελεύθερο διασταυρώσεων υποσύνολο T των ακμών, καθώς μια τριγωνοποίηση του V αποτελεί το μέγιστο δυνατό τέτοιο σύνολο που είναι δυνατόν να οριστεί δεδομένου του V. Η Διπλωματική αυτή Εργασία αφορά στη μελέτη μιας οικογένειας προβλημάτων ύπαρξης τριγωνοποίησης και την ταξινόμησή τους ως προς την πολυπλοκότητα απόφασης, αλλά και μέτρησης. Από αυτά, το γενικό πρόβλημα απόφασης είναι το μόνο μελετημένο στη βιβλιογραφία (Lloyd, 1977, NP-δύσκολο), ενώ εμείς μελετάμε αφενός την ειδική περίπτωση των κυρτών γεωμετρικών γραφημάτων, αφετέρου ένα "ενδιάμεσο" πρόβλημα ύπαρξης τριγωνοποιημένου πολυγώνου, δημιουργώντας έναν νέο 2 x 2 πίνακα αποτελεσμάτων. Στο τελευταίο κεφάλαιο, τροποποιούμε το πλαίσιο της δουλειάς μας έτσι ώστε να κατασκευάσουμε έναν αλγόριθμο για ομοιόμορφη δειγματοληψία και βέλτιστη κωδικοποίηση των κυρτών τριγωνοποιήσεων, ο οποίος υπερέχει έναντι κάθε γνωστού αλγορίθμου έως σήμερα.
(EL)
A geometric graph is a set of points V on the plane and a set of straight line segments E with endpoints in V, potentially and instinctively associated with the abstract G(V,E). When studying its thickness, i.e. partitioning its edges into crossing-free subsets (an NP-hard optimization problem), the problem of triangulation existence as a crossing-free subset T of the edges naturally occurs, as a triangulation of V is the largest such possible set that may be defined on V. In this Thesis, we examine a family of triangulation existence problems and classify them with respect to their complexity, both for their decision and their counting versions. The general case decision problem is the only one appearing in bibliography (Lloyd, 1977, NP-hard), while we deal with the convex case restriction and an "intermediate" polygon triangulation existence problem, fixing a new 2 by 2 table of results. In the final chapter, we modify our framework in order to build an exact uniform sampling and optimal coding algorithm for convex triangulations, which outperforms any known algorithm to date.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
