Back to search

National and Kapodistrian University of Athens

TRIANGULATION PROBLEMS ON GEOMETRIC GRAPHS - SAMPLING OVER CONVEX TRIANGULATIONS

Abstract

dc:description

Γεωμετρικό γράφημα καλείται ένα σύνολο σημείων V στο επίπεδο μαζί με ένα σύνολο ευθυγράμμων τμημάτων (ακμών) E που έχουν τα άκρα τους στο V, και εύκολα συσχετίζεται με το "αφηρημένο" γράφημα G(V,E). Μελετώντας το πάχος του, δηλαδή τη διαμέριση των ακμών του σε υποσύνολα ελεύθερα διασταυρώσεων (ένα NP-δύσκολο πρόβλημα βελτιστοποίησης), προκύπτει και το πρόβλημα της ύπαρξης τριγωνοποίησης ως ένα ελεύθερο διασταυρώσεων υποσύνολο T των ακμών, καθώς μια τριγωνοποίηση του V αποτελεί το μέγιστο δυνατό τέτοιο σύνολο που είναι δυνατόν να οριστεί δεδομένου του V. Η Διπλωματική αυτή Εργασία αφορά στη μελέτη μιας οικογένειας προβλημάτων ύπαρξης τριγωνοποίησης και την ταξινόμησή τους ως προς την πολυπλοκότητα απόφασης, αλλά και μέτρησης. Από αυτά, το γενικό πρόβλημα απόφασης είναι το μόνο μελετημένο στη βιβλιογραφία (Lloyd, 1977, NP-δύσκολο), ενώ εμείς μελετάμε αφενός την ειδική περίπτωση των κυρτών γεωμετρικών γραφημάτων, αφετέρου ένα "ενδιάμεσο" πρόβλημα ύπαρξης τριγωνοποιημένου πολυγώνου, δημιουργώντας έναν νέο 2 x 2 πίνακα αποτελεσμάτων. Στο τελευταίο κεφάλαιο, τροποποιούμε το πλαίσιο της δουλειάς μας έτσι ώστε να κατασκευάσουμε έναν αλγόριθμο για ομοιόμορφη δειγματοληψία και βέλτιστη κωδικοποίηση των κυρτών τριγωνοποιήσεων, ο οποίος υπερέχει έναντι κάθε γνωστού αλγορίθμου έως σήμερα.

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Αγγελόπουλος Αλέξανδρος
  • Angelopoulos Alexandros

Subjects

dc:subject × 2

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:2286251

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Αγγελόπουλος Αλέξανδρος; Angelopoulos Alexandros. TRIANGULATION PROBLEMS ON GEOMETRIC GRAPHS - SAMPLING OVER CONVEX TRIANGULATIONS. 2017. https://pergamos.lib.uoa.gr/uoa/dl/object/2286251