Αποδοτικοί Αλγόριθμοι Για Τον Υπολογισμό Του Μέγιστου Άδειου Κύβου Σε Χώρους Με Εμπόδια

Abstract

Η υπολογιστική γεωμετρία είναι ένας κλάδος της επιστήμης υπολογιστών, συγκεκριμένα του σχεδιασμού αλγορίθμων, που μελετάει προβλήματα γεωμετρικής φύσης. Αυτή η περιοχή έχει προσελκύσει το ενδιαφέρον στο πέρασμα των χρόνων λόγω των ποικίλων εφαρμογών της στη γραφική υπολογιστών, τη ρομποτική και άλλους τομείς.Η εφαρμογή που ενέπνευσε τη μελέτη αυτής της εργασίας αφορά την περιοχή της σχεδίασης ηλεκτρονικών κυκλωμάτων. Προκειμένου να επιτευχθεί μια ακριβής προσομοίωση ενός ολοκληρωμένου κυκλώματος, κάποιες παρασιτικές συνιστώσες του πρέπει να μοντελοποιηθούν. Ένα σημαντικό βήμα της διαδικασίας αυτής περιλαμβάνει τον υπολογισμό του μέγιστου άδειου κύβου με δεδομένο κέντρο που μπορεί να τοποθετηθεί ανάμεσα στους αγωγούς. Αυτός ο υπολογισμός πρέπει να επαναληφθεί πολλές φορές και, επομένως, ένας αποδοτικός αλγόριθμος είναι απαραίτητος. Αυτό το πρόβλημα είναι στενά συνδεδεμένο με θεμελιώδη προβλήματα της υπολογιστικής γεωμετρίας, όπως η αναζήτηση του μέγιστου άδειου ορθογωνίου ανάμεσα σε σημεία και το πρόβλημα του πλησιέστερου γείτονα, τα οποία βρίσκουν εφαρμογή σε πολλούς τομείς, όπως η αναγνώριση προτύπων, η εξόρυξη δεδομένων και η κατασκευή υλικών. Σε αυτήν την εργασία, περιγράφουμε αυτά και άλλα σχετικά προβλήματα και σκιαγραφούμε κάποιες από τις προτεινόμενες λύσεις τους.Στη συνέχεια, παρουσιάζεται το κυρίως μέρος της εργασίας. Αρχικά, επικεντρωνόμαστε στις γεωμετρίες Manhattan, όπου ο ζητούμενος κύβος και όλα τα εμπόδια είναι ευθυγραμμισμένα με τους άξονες. Η δομή δεδομένων που χρησιμοποιείται ονομάζεται octree. Ο αλγόριθμος στηρίζεται στην εισαγωγή των εμποδίων στους κατάλληλους κόμβους του δέντρου, έτσι ώστε κάθε αναζήτηση να εξετάζει μόνο τα γειτονικά εμπόδια του δοσμένου κέντρου. Όταν το πλησιέστερο εμπόδιο εντοπιστεί, υπολογίζεται ο μέγιστος άδειος κύβος που εφάπτεται σε αυτό. Έπειτα, ο αλγόριθμος γενικεύεται για non-Manhattan γεωμετρίες. Τα εμπόδια μπορεί να είναι πολυγωνικά ή περιστραμμένα ορθογώνια παραλληλεπίπεδα γύρω από τον άξονα z κατά γωνία φ, όπου φ ο προσανατολισμός της ακμής κάποιου εμποδίου.Τέλος, προτείνονται κάποιες τεχνικές βελτιστοποίησης και ακολουθεί μια πειραματική μελέτη για την αξιολόγηση της επίδοσης του αλγορίθμου. Συγκεκριμένα, υλοποιούμε τον αλγόριθμο σε C++ και χρησιμοποιούμε διάφορα σετ εισόδου για να αξιολογήσουμε τη χρονική επίδοση και τη χρήση της μνήμης κατά την κατασκευή του δέντρου και την πραγματοποίηση των αναζητήσεων.