| Περίληψη: | Τα δυναμικά κυρτά κύτη συνιστούν ένα σημαντικό κομμάτι του τομέα της υπολογιστικής γεωμετρίας, και η ανάπτυξη αποδοτικών αλγορίθμων για τον υπολογισμό και συντήρηση τους, είναι ένα πρόβλημα το οποίο έχει εκτενώς μελετηθεί.
Παρά το γεγονός πως έχουν παρουσιαστεί αλγόριθμοι που προσεγγίζουν οριακά την βέλτιστη λύση, εξετάζουμε την πρώτη λύση του προβλήματος που παρουσιάστηκε από τους Overmars & Van Leeuwen.
Ο αλγόριθμος των Overmars & Van Leeuwen μπορεί να έχει ξεπεραστεί θεωρητικά και πρακτικά, μα βρίσκει ακόμα πρακτικές εφαρμογές ακομά και σήμερα.
Στην παρούσα εργασία προτείνουμε μία υπολογιστικά αποδοτική υλοποίηση του αλγορίθμου τους, η οποία βασίζεται στη δομή δεδομένων γνωστή ως (2,4)-δένδρο.
Συγκεκριμένα εισαγάγουμε μία, πληροφοριακά επαυξημένη, φυλλοπροσανατολισμένη εκδοχή της σαν βάση της πλήρους δομής δεδομένων μας, αναπτύσσοντας επίσης μία αλγοριθμικά
εμπλουτισμένη εκδοχή της για την αποθήκευση των κυρτών τόξων που επιθυμούμε να υπολογίσουμε, ακολουθώντας το πρότυπο των Concatenable Queue δομών δεδομένων.
Τέλος εξετάζουμε τις επιδόσεις του προτεινόμενου αλγόριθμου, μέσω εκτενών συγκρίσεων με παρεμφερείς υλοποιήσεις, σε ρεαλιστικά σενάρια.
|
|---|
