Ημερολόγιο

Τι είναι Υπολογιστική Γεωμετρία? Σύνδεση με Aλγόριθμους, γραφικά, Εξόρυξη δεδομένων, εφαρμογές στην βιοπληροφορική (εικόνα μοριακής πρόσδεσης στα δεξιά).

2d κυρτό περίβλημα (CH2). Κάτω φράγμα μέσω Sorting. Aλγόριθμος περιτύλιξης (Jarvis, βλ. εικόνα δεξιά). Kατηγόρημα Προσανατολισμού, ή CCW (counter-clockwise) για 3 σημεία. Αυξητικός αλγόριθμος (Βeneath-beyond), σημεία σε γενική θέση.

Demos παλαιότερων ασκήσεων: Wrap2D, Marriage-before-Conquest, 3d CH. Μ.Ζερβός, Δανελάκης-Σαϊτη.

Θεωρητική άσκηση 1 (eclass, για 22/3).

Επέκταση σε 3Δ (μόριο fullerene C_60 δεξιά). Γενική διάσταση, πολύεδρα, έδρες, όψεις. Είδη πολύεδρων: άπλοκα/απλά/απλοειδή πολύεδρα, (υπερ)επίπεδα στήριξης, ημιχώροι, κώνοι καθέτων. Αναπαράσταση πολυέδρων.

Αυξητικός αλγόριθμος σε 3 (+γενικές) διαστάσεις, Kατηγόρημα προσανατολισμού. Πολυπλοκότητα χειρότερης περίπτωσης, Θεώρημα McMullen άνω φράγματος.

Περιτύλιξη και πολυπλοκότητα χρόνου/χώρου σε 3 διαστάσεις: Πολυπλοκότητα ευαίσθητη εξόδου. Αντίστροφη αναζήτηση στις έδρες: επικαλύπτον δένδρο από τον αλγόριθμο Simplex, πλήρης διάταξη εδρών.

Δυϊσμός. Γραμμικός προγραμματισμός, αλγόριθμος Simplex. Ακραία σημεία.

Εισαγωγή CGAL: Προβλήματα υλοποίησης, πλεονεκτήματα CGAL, δομή βιβλιοθήκης (πυρήνες, STL κλπ).

Προγραμματιστική 0 για 6/4.

Δυϊσμός σημείων-ευθειών σε 2D, σημείων-επιπέδων σε 3D. Ισοδυναμία υπολογισμού Ανω περιβλήματος και Τομής ημιεπιπέδων.

Delaunay (κανονική) τριγωνοποίηση σε 2d. Κάτω φράγμα μέσω CH2. Aλγόριθμοι, εναλλαγή (flip) ακμής. Κατηγόρημα InCircle. Κατασκευή μέσω προβολής 3d κυρτού περιβληματος.

Διάγραμμα Voronoi, επεκταση σε γενική διάσταση. Κατασκευή από προβολή τομής ημιχώρων. demo.

Κάτω/άνω περίβλημα, προβολή, κανονικές τριγωνοποιήσεις. [Βιβλίο "Triangulations" by DeLoera, Rambau, Santos (pp.5-36,41-57-72)]

Γεωμετρική και ορθογώνια αναζήτηση σε 1, 2, 3 (και ψηλότερες διαστάσεις): kd-δένδρα (βλ. δεξιά), δένδρα περιοχής. Κλασματική επαλληλία.

Δένδρα προτεραιότητας ως συνδυασμός δυαδικού δένδρου αναζήτησης και ουράς προτεραιότητας.

Εφαρμογές σε πολύπλοκα προβλήματα, προβλήματα μεγάλης διαστασης, εξορυξη δεδομένων.

Quadtrees (εικόνα δεξιά: octrees από Youtube, Ψαλλίδας 2010). Εντοπισμός σημείου: στο επίπεδο, σε επίπεδη τριγωνοποίηση, στον χώρο, κλπ.

Εύρεση Πλησιέστερου γείτονα: ακριβής και προσεγγιστική. Σχεδιασμός αποδοτικών δομών δεδομένων ως προς την χωρική πολυπλοκότητα και τον χρόνο προσπέλασης. Προσεγγιστικά διαγράμματα Voronoi (δεξιά εικόνα). Hashing τοπικής ευαισθησίας (Locality sensitive hashing).

Μη κυρτά, Απλά πολύγωνα και τριγωνοποιήσεις. Ορατότητα. Φύλαξη πολύγωνου: Πρόβλημα μουσείου και θεώρημα. Τοποθέτηση ⌊n/3⌋ φρουρών από τριγωνοποίηση (βλ. δεξιά). NP-hardness για την ελαχιστοποίηση του πλήθους φρουρών.

Οπτικοποίηση αποτελεσμάτων και Γραφικό input/output με τη βιβλιοθήκη "visual" της Python (slides).