Οι κινητικές δομές δεδομένων 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, η οποία πιστοποιεί τη μη-σύγκρουσή των πολυγώνων. / Kinetic Data Structures (KDSs) are a new framework for designing and
analyzing algorithms for geometrics objects (segments, polygons, disks etc.) in
motion. Our goal is to maintain an attribute of a set of moving objects, for example
the convex hull or the closest pair. The maintenance of the attribute is made through a set of conditions that guarantee the validity of the structure every moment. This set is changed with time due to the motion. The conditions are stored in a queue ordered
chronologically. Every time the attribute is changed, we update the structure and the
queue.
The first chapter is an introduction to the KDSs. We mention basic notions and
ideas of the KDSs, like: configuration function, certificates, critical events.
Furthermore, we discuss their measure of performance.
In the second chapter we deal with the Binary Space Partitions (BSPs), first in
static and then in kinetic environment. Specifically, we present three algorithms for
the maintenance of a BSP for a set of moving segments in the plane. According to the
first known algorithm which was proposed for efficiently maintaining the BSP for a
set of non-intersecting segments S in the plane using the philosophy of KDSs, we
construct a BSP - considering that the segments are static - and then we maintain it as the segments move. The second algorithm is substantially an expansion of the first
algorithm as it deals with the same problem, but for intersecting segments. The set of
the certificates is changed as well as the set of critical events. The third algorithm uses a different technique for the construction and maintenance of the BSP for the set S. It is an improvement of the first algorithm.
In the third chapter, we deal with the maintenance of the Voronoi diagram
(VD) for a set of moving, probably intersecting disks in the plane and the
maintenance of a compact Voronoi-like diagram for a set of non-intersecting, convex
polygons in the plane (compact VD is dual to VD, except that its size is a function of
the number of polygons and not of the number of vertices). In both cases, we solve the
problem by maintaining the dual graph of VD, the Delaunay triangulation (DT ). The
maintenance of the DT is based in the fact that a set of local conditions (InCircle
tests) guarantee the total correctness of the structure and we are able to do only local
changes. So, as the objects move, we have a valid DT every moment and
consequently a valid VD.
Finally, we mention a KDS for detecting collisions between two simple
polygons in motion. In order to do so, we create a planar subdivision of the free space
between the polygons, called External Relative Geodesic Triangulation, which certify their disjointness.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/890 |
| Date | 29 August 2008 |
| Creators | Τσιμά, Αλεξάνδρα |
| Contributors | Αλεβίζος, Παναγιώτης, Αλεβίζος, Παναγιώτης |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0033 seconds