Παρουσίαση/Προβολή
(M169 (ΠΜΣ 560)) - Γιάννης Εμίρης, Ileana Streinu
Περιγραφή Μαθήματος
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/.
Ημερομηνία δημιουργίας
Τρίτη 2 Δεκεμβρίου 2
-
Grading
A. Take home assignment, up to 1/4
B. Class participation 5%
C. Course project (oral presenations & final report), the rest.
Class presentations should use PDF / ΡΡΤ files to discuss and critically present their topic. At the end of the exam period (early July) students submit a full report discussing / comparing their papers, possibly open questions and future work. Also any experiments and code they developed.Course Syllabus
March 8: Intro and convexity (Yiannis Emiris)
March 15: Convex hull in the plane (Yiannis)
March 22: Polytope and linear programming (Yiannis)
March 29: Convex hull in 3d and general dimension (Yiannis)
April 5: Robot arms and origami folding (Ileana Streinu)
April 12: Rigidity and flexibility (Ιleana)
April 19: Random sampling, polytope volume (Vissarion Fisikopoulos)
April 26: Periodic rigidity, crystallography and auxetics (Ιleana)
May 17: Course projects discussed, roadmaps presented.
May 24: Project progress presentations
May 31: Project final oral presentations / Guest lecture on Voronoi for IC design
Last one: Participate in SoCG on 11-14/6