E-Locus - Ιδρυματικό Καταθετήριο Πανεπιστημίου Κρήτης - Κατηγορήματα Ευκλείδειου διαγράμματος Voronoi ευθύγραμμων τμημάτων τα οποία είναι παράλληλα ή υπό γωνία 45 με τους άξονες

Αρχική Κατηγορήματα Ευκλείδειου διαγράμματος Voronoi ευθύγραμμων τμημάτων τα οποία είναι παράλληλα ή υπό γωνία 45 με τους άξονες

Αποτελέσματα - Λεπτομέρειες

[Προσθήκη στο καλάθι]

Κωδικός Πόρου

000369014

Τίτλος

Κατηγορήματα Ευκλείδειου διαγράμματος Voronoi ευθύγραμμων τμημάτων τα οποία είναι παράλληλα ή υπό γωνία 45 με τους άξονες

Άλλος τίτλος

Predicates for the Euclidean Voronoi Diagram of Axis-Aligned and Ortho-45 Line Segments

Συγγραφέας

Καμαριανάκης, Εμμανουήλ Νικολάου

Σύμβουλος διατριβής

Καραβέλας, Μενέλαος

Περίληψη

Στην εργασία αυτή μελετάμε το πιο απαιτητικό κατηγόρημα που απαιτείται για τον υπολογισμό του Ευκλείδειου Διαγράμματος Voronoi Ευθυγράμμων Τμημάτων τα οποία είναι παράλληλα ή υπό γωνία 45° με τους άξονες, το λεγόμενο Incircle predicate. Ο κύριος στόχος μας είναι να ελαχιστοποιήσουμε τον μέγιστο αλγεβρικό βαθμό. Στην ανάλυση του κατηγορήματος για την περίπτωση όπου τα τμήματα είναι παράλληλα με τους άξονες δείχνουμε ότι το κατηγόρημα Incircle μπορεί να απαντηθεί υπολογίζοντας αλγεβρικές παραστάσεις που έχουν μέγιστο βαθμό 6, σε αντίθεση με τις μέχρι τώρα με¬θόδους οι οποίες απαιτούσαν τον διπλάσιο βαθμό. Για να το καταφέρουμε αυτό, ανάγουμε το κατηγόρημα στην σύγκριση δύο αποστάσεων (σε αντίθεση με την σύγκριση τετραγώνων δύο αποστάσεων σε άλλες μεθόδους) και επιπλέον ανάγουμε την σύγκριση αυτή στον υ¬πολογισμό του προσήμου ενός (γραμμικού ή δευτεροβάθμιου) πολυωνύμου (ως προς μια μεταβλητή) σε μία συγκεκριμένη ρίζα ενός δευτεροβάθμιου πολυωνύμου (πάλι ως προς μία μεταβλητή). Αντίστοιχα, δείχνουμε ότι για τον υπολογισμό του κατηγορήματος Incircle για την περίπτωση ευθυγράμμων τμημάτων παράλληλα ή υπό γωνία 45° με τους άξονες μπορεί να απαντηθεί υπολογίζοντας αλγεβρικές παραστάσεις που έχουν μέγιστο βαθμό 12. Αυτός είναι και ο καλύτερος βαθμός που μπορεί να επιτευχθεί όταν υπάρχουν τμήματα τα οποία δεν είναι παράλληλα ή κάθετα μεταξύ τους.

Φυσική περιγραφή

99 σ. : εικ., πίν. ; 30 εκ.

Γλώσσα

Ελληνικά

Θέμα

Ευθύγραμμα τμήματα

Ευκλείδειο διάγραμμα Voronoi

Κατηγόρημα Incircle

Παράλληλα με τους αξόνες

Υπολογιστική Γεωμετρία

Υπό γωνία 45 με τους άξονες

Ημερομηνία έκδοσης