Περιγραφή Μαθήματος

Eισαγωγή στους Γεωμετρικούς Αλγόριθμους και προεκτάσεις προς τις ερευνητικά ενεργές περιοχές της Υπολογιστικής Γεωμετρίας. Η ύλη μεταβάλλεται κάθε χρόνο, σε κάποιο βαθμό. Kυρτότητα: Κυρτό περίβλημα (convex hull) σε 2 και 3 διαστάσεις, αυξητικός αλγόριθμος, αλγόριθμος περιτύλιξης και πολυπλοκότητα ευαίσθητη εξόδου (output sensitive), μέθοδος Διαίρει και βασίλευε. Άθροισμα Minkowski πολυέδρων. Γραμμική βελτιστοποίηση (ή γραμμικός προγραμματισμός), δυϊσμός, τυχαιότητα. Ζητήματα υλοποίησης, εκφυλισμένα δεδομένα και διαταραχή. Τριγωνοποιήσεις: Διάγραμμα Voronoi και κατασκευή ως προβολή πολυέδρου, τριγωνοποίηση Delaunay και δυϊσμός με το Διάγραμμα Voronoi, εφαρμογές στη δομική μοριακή βιολογία, στην κίνηση ρομπότ ανάμεσα σε εμπόδια, και την κατασκευή πλέγματος (mesh). Προβλήματα ορατότητας, φύλαξη μουσείου (art gallery), τριγωνοποίηση σε 2 διαστάσεις, μέθοδος σάρωσης. Γεωμετρική αναζήτηση: Δομές γεωμετρικών δεδομένων, αναζήτηση περιοχής (range search) σε 2 και περισσότερες διαστάσεις, (προσεγγιστική) εύρεση πλησιέστερου γείτονα με δενδρικές δομές ή πίνακες κατακερματισμού, εφαρμογές σε Εξόρυξη δεδομένων και Γεωγραφικά Συστήματα πληροφόρησης (GIS). Υλοποιήσεις σε Python και CGAL/C++.

Video-Διαλέξεις