Δυναμικά κυρτά κύτη σε 2-4 δέντρα
Τα δυναμικά κυρτά κύτη συνιστούν ένα σημαντικό κομμάτι του τομέα της υπολογιστικής γεωμετρίας, και η ανάπτυξη αποδοτικών αλγορίθμων για τον υπολογισμό και συντήρηση τους, είναι ένα πρόβλημα το οποίο έχει εκτενώς μελετηθεί. Παρά το γεγονός πως έχουν παρουσιαστεί αλγόριθμοι που προσεγγίζουν οριακά τ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2021
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/14997 |
| id |
nemertes-10889-14997 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-149972022-09-05T06:57:23Z Δυναμικά κυρτά κύτη σε 2-4 δέντρα Dynamic convex hulls in 2-4 trees Παυλίδης, Ευριπίδης Pavlidis, Evripidis Δυναμικά κυρτά περιβλήματα Δυναμικά κυρτά κύτη Κύτη Dynamic convex hull Convex hull Hull Τα δυναμικά κυρτά κύτη συνιστούν ένα σημαντικό κομμάτι του τομέα της υπολογιστικής γεωμετρίας, και η ανάπτυξη αποδοτικών αλγορίθμων για τον υπολογισμό και συντήρηση τους, είναι ένα πρόβλημα το οποίο έχει εκτενώς μελετηθεί. Παρά το γεγονός πως έχουν παρουσιαστεί αλγόριθμοι που προσεγγίζουν οριακά την βέλτιστη λύση, εξετάζουμε την πρώτη λύση του προβλήματος που παρουσιάστηκε από τους Overmars & Van Leeuwen. Ο αλγόριθμος των Overmars & Van Leeuwen μπορεί να έχει ξεπεραστεί θεωρητικά και πρακτικά, μα βρίσκει ακόμα πρακτικές εφαρμογές ακομά και σήμερα. Στην παρούσα εργασία προτείνουμε μία υπολογιστικά αποδοτική υλοποίηση του αλγορίθμου τους, η οποία βασίζεται στη δομή δεδομένων γνωστή ως (2,4)-δένδρο. Συγκεκριμένα εισαγάγουμε μία, πληροφοριακά επαυξημένη, φυλλοπροσανατολισμένη εκδοχή της σαν βάση της πλήρους δομής δεδομένων μας, αναπτύσσοντας επίσης μία αλγοριθμικά εμπλουτισμένη εκδοχή της για την αποθήκευση των κυρτών τόξων που επιθυμούμε να υπολογίσουμε, ακολουθώντας το πρότυπο των Concatenable Queue δομών δεδομένων. Τέλος εξετάζουμε τις επιδόσεις του προτεινόμενου αλγόριθμου, μέσω εκτενών συγκρίσεων με παρεμφερείς υλοποιήσεις, σε ρεαλιστικά σενάρια. Dynamic Convex Hulls constitute an important part of the field of computational geometry, and the development of efficient algorithms for their calculation and maintenance is a problem that has been extensively studied. Despite the fact that algorithms, that marginally approach the optimal solution, have been introduced, we consider the first solution presented by Overmars and Van Leeuwen. Overmars' and Van Leeuwen's algorithm may have been surpassed in theory and practice, but it still finds practical applications today. In the present work we propose a computationally efficient implementation, of their algorithm, which is based on the data structure known as 2-4 Tree. Specifically, we introduce an informatively augmented, leaf-oriented version of it as the basis of our complete data structure, also developing an algorithmically enriched version of it, to store the convex arcs we want to calculate, following the template of Concatenable Queue data structures. Finally, we examine the performance of the proposed algorithm, through extensive comparisons with similarly implementations, in realistic scenarios. 2021-07-13T07:15:02Z 2021-07-13T07:15:02Z 2021-07-08 http://hdl.handle.net/10889/14997 gr application/pdf application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Δυναμικά κυρτά περιβλήματα Δυναμικά κυρτά κύτη Κύτη Dynamic convex hull Convex hull Hull |
| spellingShingle |
Δυναμικά κυρτά περιβλήματα Δυναμικά κυρτά κύτη Κύτη Dynamic convex hull Convex hull Hull Παυλίδης, Ευριπίδης Δυναμικά κυρτά κύτη σε 2-4 δέντρα |
| description |
Τα δυναμικά κυρτά κύτη συνιστούν ένα σημαντικό κομμάτι του τομέα της υπολογιστικής γεωμετρίας, και η ανάπτυξη αποδοτικών αλγορίθμων για τον υπολογισμό και συντήρηση τους, είναι ένα πρόβλημα το οποίο έχει εκτενώς μελετηθεί.
Παρά το γεγονός πως έχουν παρουσιαστεί αλγόριθμοι που προσεγγίζουν οριακά την βέλτιστη λύση, εξετάζουμε την πρώτη λύση του προβλήματος που παρουσιάστηκε από τους Overmars & Van Leeuwen.
Ο αλγόριθμος των Overmars & Van Leeuwen μπορεί να έχει ξεπεραστεί θεωρητικά και πρακτικά, μα βρίσκει ακόμα πρακτικές εφαρμογές ακομά και σήμερα.
Στην παρούσα εργασία προτείνουμε μία υπολογιστικά αποδοτική υλοποίηση του αλγορίθμου τους, η οποία βασίζεται στη δομή δεδομένων γνωστή ως (2,4)-δένδρο.
Συγκεκριμένα εισαγάγουμε μία, πληροφοριακά επαυξημένη, φυλλοπροσανατολισμένη εκδοχή της σαν βάση της πλήρους δομής δεδομένων μας, αναπτύσσοντας επίσης μία αλγοριθμικά
εμπλουτισμένη εκδοχή της για την αποθήκευση των κυρτών τόξων που επιθυμούμε να υπολογίσουμε, ακολουθώντας το πρότυπο των Concatenable Queue δομών δεδομένων.
Τέλος εξετάζουμε τις επιδόσεις του προτεινόμενου αλγόριθμου, μέσω εκτενών συγκρίσεων με παρεμφερείς υλοποιήσεις, σε ρεαλιστικά σενάρια. |
| author2 |
Pavlidis, Evripidis |
| author_facet |
Pavlidis, Evripidis Παυλίδης, Ευριπίδης |
| author |
Παυλίδης, Ευριπίδης |
| author_sort |
Παυλίδης, Ευριπίδης |
| title |
Δυναμικά κυρτά κύτη σε 2-4 δέντρα |
| title_short |
Δυναμικά κυρτά κύτη σε 2-4 δέντρα |
| title_full |
Δυναμικά κυρτά κύτη σε 2-4 δέντρα |
| title_fullStr |
Δυναμικά κυρτά κύτη σε 2-4 δέντρα |
| title_full_unstemmed |
Δυναμικά κυρτά κύτη σε 2-4 δέντρα |
| title_sort |
δυναμικά κυρτά κύτη σε 2-4 δέντρα |
| publishDate |
2021 |
| url |
http://hdl.handle.net/10889/14997 |
| work_keys_str_mv |
AT paulidēseuripidēs dynamikakyrtakytēse24dentra AT paulidēseuripidēs dynamicconvexhullsin24trees |
| _version_ |
1771297167830417408 |
