Κυρτό περίβλημα σε 2, 3 και μεγαλύτερες διάστασεις, αλγόριθμος περιτύλιξης (πολυπλοκότητα ευαίσθητη εξόδου) και αυξητικός αλγόριθμος. Αθροισμα Minkowski. Τριγωνοποίηση πολυγώνου. Eκφυλισμένα δεδομένα, διαταραχή. Γραμμικός Προγραμματισμός, αλγόριθμος Simplex και αντίστροφη αναζήτηση, δυϊσμός και πόλωση. Διάγραμμα Voronoi, αναγωγή σε ΚΠ. Τριγωνοποίηση Delaunay, α-σχήματα και εφαρμογές στην δομική βιοπληροφορική, στην κίνηση ρομπότ ανάμεσα σε εμπόδια. Διατάξεις ευθυγράμμων τμημάτων, ευθειών. Δομές γεωμετρικών δεδομένων. Εντοπισμός και εξόρυξη δεδομένων, ορθoγώνια αναζήτηση, kd-δένδρα, δένδρα περιοχών. Προσεγγιστική εύρεση πλησιέστερου γείτονα με δενδρικές δομές ή πίνακες κατακερματισμού σε μεγάλες διαστάσεις και γενικούς μετρικούς χώρους. Locality-sensitive Hashing για την αντιμετώπιση της "κατάρας της διάστασης". Mείωση διάστασης με τυχαιοκρατικές προβολές και το Λήμμα Johnson-Lindenstrauss. Εφαρμογές στη συσταδοποίηση. Υλοποίηση σε Python και στην C++ βιβλιοθήκη γεωμετρικού λογισμικού CGAL.
Type
Elective
Course Description