Εφαρμογή των κινητικών δομών δεδομένων σε προβλήματα της υπολογιστικής γεωμετρίας

• Κύριος συγγραφέας: Τσιμά, Αλεξάνδρα
• Άλλοι συγγραφείς: Αλεβίζος, Παναγιώτης
• Μορφή: Thesis
• Γλώσσα: Greek
• Έκδοση: 2008
• Θέματα: Υπολογιστική γεωμετρία; Κινητικές δομές δεδομένων; Computational geometry; Kinetic data structures; 511.3

Οι κινητικές δομές δεδομένων KDSs (kinetic data structures) είναι ένα νέο πλαίσιο εργασίας για το σχεδιασμό και την ανάλυση αλγορίθμων σχετικών με γεωμε- τρικά αντικείμενα (ευθύγραμμα τμήματα, πολύγωνα, δίσκοι κ.τ.λ.) σε κίνηση. Σκο- πός μας είναι να διατηρήσουμε ένα χαρακτηριστικό ενός συνόλου κινούμενων αντι- κειμένων, π.χ. την κυρτή θήκη ή το κοντινότερο ζευγάρι του. Η διατήρηση του χαρα κτηριστικού γίνεται μέσω ενός συνόλου συνθηκών που εγγυώνται την εγκυρότητα της δομής κάθε χρονική στιγμή και το οποίο μεταβάλλεται με το χρόνο λόγω της κίνησης. Οι συνθήκες αποθηκεύονται σε μια ουρά διατεταγμένες χρονολογικά. Κάθε φορά που αλλάζει το χαρακτηριστικό που μας ενδιαφέρει ενημερώνουμε τη δομή μας και την ουρά. Η πρώτη ενότητα της εργασίας είναι μια εισαγωγή στις KDSs. Αναφέρουμε βασικές έννοιες και ιδέες των KDSs όπως: συνάρτηση διαμόρφωσης, πιστοποιητικά, κρίσιμα γεγονότα. Επίσης, ασχολούμαστε και με τα μέτρα απόδοσής τους. Στη δεύτερη ενότητα ασχολούμαστε με τους δυαδικούς διαχωρισμούς χώρου BSPs, πρώτα σε στατικό και κατόπιν σε κινητικό περιβάλλον. Συγκεκριμένα παρουσιάζουμε τρεις αλγορίθμους για τη διατήρηση του BSP ενός συνόλου κινούμενων ευθυγράμμων τμημάτων στο επίπεδο. Σύμφωνα με τον πρώτο γνωστό αλγόριθμο που διατυπώθηκε για την αποτελεσματική διατήρηση του BSP για ένα σύνολο μη-τεμνόμενων ευθυγράμμων τμημάτων S στο επίπεδο χρησιμοποιώντας τη φιλοσοφία των KDSs, κατασκευάζουμε έναν BSP για το S θεωρώντας τα ευθύγραμμα τμήματα στάσιμα και στη συνέχεια τον διατηρούμε καθώς αυτά κινούνται. Ο δεύτερος αλγόριθμος είναι ουσιαστικά μια επέκταση του πρώτου καθώς ασχολείται με το ίδιο πρόβλημα, αλλά για τεμνόμενα ευθύγραμμα τμήματα. Αλλάζει το σύνολο των πιστοποιητικών και οι τρόποι με τους οποίους μπορεί να αλλάξει η δομή του BSP. Ο τρίτος αλγόριθμος χρησιμοποιεί ένα διαφορετικό τρόπο για την κατασκευή και διατήρηση του BSP για το σύνολο S βελτιώνοντας τον αρχικό. Στην τρίτη ενότητα ασχολούμαστε με τη διατήρηση του Voronoi διαγράμματος (VD) για ένα σύνολο κινούμενων, πιθανώς τεμνόμενων δίσκων στο επίπεδο και του συμπαγούς Voronoi διαγράμματος για ένα σύνολο μη-τεμνόμενων κυρτών πολυγώνων στο επίπεδο (το συμπαγές VD είναι δυϊκό του VD, αλλά το μέγεθός του είναι συνάρτηση του αριθμού των πολυγώνων και όχι του αριθμού των κορυφών). Και στις δύο περιπτώσεις, η επίλυση του προβλήματος ανάγεται στη διατήρηση του δυϊκού του VD, της τριγωνοποίησης Delaunay DT . Η διατήρηση της DT βασίζεται στο γεγονός ότι ένα σύνολο τοπικών συνθηκών (έλεγχοι InCircle), πιστοποιούν την ολική ορθότητα της δομής και τοπικές επιδιορθώσεις είναι πάντα εφικτές. Έτσι, καθώς τα αντικείμενα κινούνται, έχουμε κάθε στιγμή μια έγκυρη DT και συνεπώς ένα έγκυρο VD. Τέλος, αναφέρουμε μια KDS για τον εντοπισμό συγκρούσεων μεταξύ δύο απλών πολυγώνων σε κίνηση. Ο αλγόριθμος διατηρεί μια υποδιαίρεση του ελεύθερου χώρου μεταξύ των πολυγώνων, που καλείται external relative geodesic triangulation, η οποία πιστοποιεί τη μη-σύγκρουσή των πολυγώνων.