Course : Yπολογιστική Γεωμετρία / Computational Geometry

Graduate course, Spring 2024, Friday 3 pm, room Δ

Intro to Geometric Algorithms and geometric combinatorics, overview of active research areas of Computational Geometry. Design and analysis of algorithms, Implementation.

Convex hulls, convexity, volume computation and approximation. Minkowski sum, polygon triangulation and regular subdivisions. Implementation issues (input degeneracy) and perturbations. Linear programming algorithms and reverse search, duality. Voronoi diagram, Delaunay triangulation, alpha-shapes.

Geometric data structures, geometric search, approximate nearest neighbors in general dimension, LSH, dimensionality reduction, randomized projections. Johnson-Lndenstrauss lemma. Curse of dimensionality and how to circumvent it. Applications to clustering.

The geometry of kinematics, linkages, and origami. Applications to bioinformatics and robotics.

%%%

Eισαγωγή στους Γεωμετρικούς Αλγόριθμους, προεκτάσεις προς τις ενεργές περιοχές της Υπολογιστικής Γεωμετρίας. Σχεδιασμός και ανάλυση αλγορίθμων. Υλοποίηση σε Python ή στην C++, βιβλιοθήκη γεωμετρικού λογισμικού CGAL.

Κυρτό περίβλημα σε 2, 3 και μεγαλύτερες διάστασεις, αλγόριθμος περιτύλιξης (πολυπλοκότητα ευαίσθητη εξόδου) και αυξητικός αλγόριθμος (πολυπλοκότητα χειρότερης περίπτωσης). Αθροισμα Minkowski. Τριγωνοποίηση Πολυγώνου (Art Gallery). Προβλήματα υλοποίησης, εκφυλισμένα δεδομένα, διαταραχή. Γραμμικός Προγραμματισμός, αλγόριθμος Simplex και αντίστροφη αναζήτηση, δυϊσμός και πόλωση. Διάγραμμα Voronoi, αναγωγή σε ΚΠ. Τριγωνοποίηση Delaunay, α-σχήματα και εφαρμογές στην δομική βιοπληροφορική, στην κίνηση ρομπότ.

Δομές και ανάλυση γεωμετρικών δεδομένων, kd-δένδρα, δένδρα περιοχών (range trees). Γεωμετρική Αναζήτηση, ορθoγώνια αναζήτηση, Προσεγγιστική εύρεση πλησιέστερου γείτονα με δενδρικές δομές ή πίνακες κατακερματισμού σε μεγάλες διαστάσεις και γενικούς μετρικούς χώρους. Locality-sensitive hashing για την αντιμετώπιση της "κατάρας της διάστασης" (curse of dimensionality). Mείωση διάστασης με τυχαιοκρατικές προβολές και το Λήμμα Johnson-Lindenstrauss. Εφαρμογές σε συσταδοποίηση (clustering).

Για το Προπτυχιακό μαθημα (μέχρι το 2023) δείτε: http://eclass.uoa.gr/courses/D42/.