TRIANGULATION PROBLEMS ON GEOMETRIC GRAPHS - SAMPLING OVER CONVEX TRIANGULATIONS

Διπλωματική Εργασία uoadl:2286251 646 Αναγνώσεις

Μονάδα:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2017-11-23
Έτος εκπόνησης:
2017
Συγγραφέας:
Αγγελόπουλος Αλέξανδρος
Στοιχεία επιβλεπόντων καθηγητών:
Αριστείδης Παγουρτζής, Αναπληρωτής Καθηγητής Ε.Μ.Π.
Ευστάθιος Ζάχος, Ομότιμος Καθηγητής Ε.Μ.Π.
Δημήτρης Φωτάκης, Επίκουρος Καθηγητής Ε.Μ.Π.
Πρωτότυπος Τίτλος:
TRIANGULATION PROBLEMS ON GEOMETRIC GRAPHS - SAMPLING OVER CONVEX TRIANGULATIONS
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
ΠΡΟΒΛΗΜΑΤΑ ΤΡΙΓΩΝΟΠΟΙΗΣΗΣ ΣΕ ΓΕΩΜΕΤΡΙΚΑ ΓΡΑΦΗΜΑΤΑ - ΔΕΙΓΜΑΤΟΛΗΨΙΑ ΚΥΡΤΩΝ ΤΡΙΓΩΝΟΠΟΙΗΣΕΩΝ
Περίληψη:
Γεωμετρικό γράφημα καλείται ένα σύνολο σημείων V στο επίπεδο μαζί με ένα σύνολο ευθυγράμμων τμημάτων (ακμών) E που έχουν τα άκρα τους στο V, και εύκολα συσχετίζεται με το "αφηρημένο" γράφημα G(V,E). Μελετώντας το πάχος του, δηλαδή τη διαμέριση των ακμών του σε υποσύνολα ελεύθερα διασταυρώσεων (ένα NP-δύσκολο πρόβλημα βελτιστοποίησης), προκύπτει και το πρόβλημα της ύπαρξης τριγωνοποίησης ως ένα ελεύθερο διασταυρώσεων υποσύνολο T των ακμών, καθώς μια τριγωνοποίηση του V αποτελεί το μέγιστο δυνατό τέτοιο σύνολο που είναι δυνατόν να οριστεί δεδομένου του V. Η Διπλωματική αυτή Εργασία αφορά στη μελέτη μιας οικογένειας προβλημάτων ύπαρξης τριγωνοποίησης και την ταξινόμησή τους ως προς την πολυπλοκότητα απόφασης, αλλά και μέτρησης. Από αυτά, το γενικό πρόβλημα απόφασης είναι το μόνο μελετημένο στη βιβλιογραφία (Lloyd, 1977, NP-δύσκολο), ενώ εμείς μελετάμε αφενός την ειδική περίπτωση των κυρτών γεωμετρικών γραφημάτων, αφετέρου ένα "ενδιάμεσο" πρόβλημα ύπαρξης τριγωνοποιημένου πολυγώνου, δημιουργώντας έναν νέο 2 x 2 πίνακα αποτελεσμάτων. Στο τελευταίο κεφάλαιο, τροποποιούμε το πλαίσιο της δουλειάς μας έτσι ώστε να κατασκευάσουμε έναν αλγόριθμο για ομοιόμορφη δειγματοληψία και βέλτιστη κωδικοποίηση των κυρτών τριγωνοποιήσεων, ο οποίος υπερέχει έναντι κάθε γνωστού αλγορίθμου έως σήμερα.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λοιπές θεματικές κατηγορίες:
Μαθηματικά
Λέξεις-κλειδιά:
γεωμετρικό γράφημα, ύπαρξη τριγωνοποίησης, πολυπλοκότητα, πολυπλοκότητα μέτρησης, δειγματοληψία κυρτών τριγωνοποιήσεων
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
1
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
42
Αριθμός σελίδων:
55