Υπολογιστική γεωμετρία με εφαρμογές σε συστήματα GIS και CAD

Abstract

In the present Thesis we have investigated interesting open problems within the research field of Discrete Geometry and related topic. We focused on the designing of fast and effective algorithms appropriate to solve modern problems of discrete derivation, discrete integration and discrete optimization appearing in current issues of natural sciences, Mathematics and Informatics. As far as the problem of discrete derivation is concerned, we developed a new method for interpolation based on the use of specially designed derivative kernels which facilitates the required numerical differentiation. Application of the method to measured spectra has shown that the unfolding procedure becomes more accurate even for spectra with rather low statistics. For the problem of discrete optimization, we constructed an algorithm relying on the simulated annealing technique in the searching for the optimal solution procedure. Its application on the calculation of the optimal ship routing problems through the minimization of the cost function including a comfort and a safety weighted part, has lead to the conclusion that the searching procedure is dramatically accelerated if we consider variations of the initial path only parallel or anti-parallel to the wave direction. The advantages of the proposed algorithm are illustrated by comparing the resulting path with those obtained by utilizing time consuming genetic algorithms. We have, furthermore, designed a parallel hybrid genetic algorithm hat is based on the fundamental characteristics of evolutionary processes to solve constrained problems, introducing a new smooth penalty function with zero derivatives at the boundaries of the feasible subspaces. The new method was applied to optimal ship routing. The efficiency of the new technique makes it applicable to operational systems. Finally, for the problem of numerical integration, within the framework of the discrete variations and discrete Lagrangian formulation, we constructed methods that are phase-fitted in order to apply them in stiff oscillatory problems and methods that are symmetric providing an improved energy behavior. Finally, we have introduced the principle of local path fitting, by which it is possible to construct variational integrators without the need of estimating the action integral

Στην παρούσα διδακτορική διατριβή μελετήθηκαν ενδιαφέροντα ανοιχτά προβλήματα τα οποία εμπίπτουν στο χώρο επικάλυψης του πεδίου έρευνας της Υπολογιστικής και Διακριτής Γεωμετρίας με τις παρεμφερείς επιστήμες. Ιδιαίτερη έμφαση δόθηκε στο σχεδιασμό ευέλικτων και λειτουργικών αλγορίθμων για την επίλυση σύγχρονων προβλημάτων διαφόρισης, ολοκλήρωσης και διακριτής βελτιστοποίησης που εμφανίζονται κυρίως στο ερευνητικό χώρο των φυσικών επιστημών, των Μαθηματικών και της Πληροφορικής. Στην πρόβλημα της διακριτής παραγώγισης αναπτύχθηκε μια νέα μέθοδος παρεμβολής η οποία στηρίζεται στη χρήση ειδικά σχεδιασμένων πυρήνων διαφόρισης οι οποίοι διευκολύνουν την αριθμητική παραγώγιση. Η εφαρμογή της σε μετρούμενα φάσματα με κορυφές μικρής στατιστικής έδειξε ότι η διαδικασία ανέλιξης καθίσταται περισσότερο ακριβής ακόμα και σε φάσματα αρκετά χαμηλής ποιότητας. Στο πρόβλημα της διακριτής βελτιστοποίησης, αναπτύχθηκε ένας αποδοτικός και λειτουργικός αλγόριθμος ο οποίος στηρίζεται στην τεχνική της θερμικής ανόπτυσης κατά την διαδικασία αναζήτησης της βέλτιστης λύσης. Η εφαρμογή του στον υπολογισμό της βέλτιστης πορείας ενός πλοίου μέσω της ελαχιστοποίησης της συνάρτησης κόστους έδειξε ότι η διαδικασία αναζήτησης επιταχύνεται θεωρώντας ένα κεντρικό αποτέλεσμα το οποίο δίνει την δυνατότητα να λάβουμε υπόψη μόνο μεταβολές της αρχικής πορείας οι οποίες είναι παράλληλες ή αντιπαράλληλες προς την κατεύθυνση του πεδίου κύματος. Τα πλεονεκτήματα του προτεινόμενου αλγορίθμου καταδεικνύονται συγκρίνοντας την προκύπτουσα πορεία με εκείνες που υπολογίστηκαν από εξαντλητικούς και χρονοβόρους γενετικούς αλγορίθμους. Σχεδιάστηκε επίσης ένας εξελικτικός υβριδικός αλγόριθμος ο οποίος στηρίζεται σε γενετικές τεχνικές για την επίλυση προβλημάτων βέλτιστης πορείας πλοίου, μέθοδος την οποία επιβάλλει ο αρκετά πολύπλοκος χώρος των υποψήφιων λύσεων. Το μεγάλο πλήθος των δεσμών οδηγεί στην ανάπτυξη ενός παράλληλου συστήματος παραγωγής λύσης σε ρεαλιστικούς χρόνους και ολοκλήρωσης της μεθόδου σε ένα λειτουργικό συμβουλευτικό σύστημα. Για το πρόβλημα της αριθμητικής ολοκλήρωσης, στα πλαίσια της θεωρίας των διακριτών μεταβολών κατασκευάστηκαν τεχνικές οι οποίες διατηρούν σημαντικές συμμετρίες του προβλήματος και είναι εξαιρετικά αποτελεσματικές σε ολοκληρώσεις μακράς περιόδου. Ταυτόχρονα τους διακρίνει μεγάλη ακρίβεια στην εκτίμηση της λύσης. Ιδιαίτερα σημαντική είναι η συνεισφορά της παρούσας έρευνας στην ανάπτυξη, για πρώτη φορά, μεθόδου τοπικής προσαρμογής, η οποία είναι συνεπής με τη θεωρία μεταβολών χωρίς την ανάγκη προσδιορισμού χρονοβόρων και πολύπλοκων εκτιμήσεων του ολοκληρώματος δράσης. Τούτο απλουστεύει δραματικά την εφαρμογή της μεθόδου και βελτιώνει σημαντικά την ενεργειακή συμπεριφορά των υπό ολοκλήρωση συστημάτων.