ΥΠΟΛΟΓΙΣΤΙΚΗ ΓΕΩΜΕΤΡΙΑ
Διδάσκων: Γιάννης Eμίρης
|
|
|
|
| εβδ.1.
(9-12/10) Εισαγωγή |
Τι είναι η Υπολογιστική Γεωμετρία; Εισαγωγή, demos. Σύνδεση
με τα γραφικά, την δομική μοριακή βιολογία, με μαθήματα θεωρητικής πληροφορικής.
Eπανάληψη: Υπολογιστικό μοντέλο, ανάλυση πολυπλοκότητας, δομές δεδομένων.
-- Κυρτό περίβλημα σε 2 διάστασεις (ΚΠ2). Φράγματα στην Πολυπλοκότητα. Aλγόριθμος τυλίγματος δώρου (gift-wrapping) στο επίπεδο. |
Demos: Περιτύλιγμα, Αλγόριθμος KS. |
| εβδ.2
Κυρτότητα |
Κατηγόρημα αριστερής στροφής CCW (counter-clockwise) για 3 δεδομένα
σημεία. Κυρτό περίβλημα σε 2 διάστασεις (ΚΠ2): Αυξητικός αλγόριθμος (beneath-beyond).
-- Μέση πολυπλοκότητα αυξητικού. ΚΠ3: αυξητικός αλγόριθμος (Beneath-beyond), επέκταση σε γενική διάσταση. Πολύεδρα, έδρες, αναπαράσταση στον υπολογιστή. |
Μια εισαγωγή στην CGAL βρίσκεται
εδώ.
Kλάσεις C++, C++ templates: δείτε αρχεία EΔΩ. |
| εβδ.3
(23-26/10) |
Πολυπλοκότητα BB3. Θεώρημα McMullen.
-- Προβλήματα υλοποίησης, εκφυλισμένα δεδομένα, διαταραχή σημείων. Γραμμική άλγεβρα για διαταραγμένα κατηγορήματα. |
|
| εβδ.4
(30/10-2/11) |
Αλγόριθμος τυλίγματος δώρου (gift-wrapping) σε 3 διαστάσεις. | Εργασία
1 για την 1/11.
SOLUTIONS: erg1intro.txt, erg1sort.C, erg1poly.C. |
| εβδ.5
Γραμμική βελτιστοποίηση (ΓΒ) (6-9/11) |
Δυϊσμός, ισοδυναμία άΠ2 με Tομή ημιεπιπέδων.
-- Γραμμική Bελτιστοποίηση: είδη αλγορίθμων. Aυξητικός αλγοριθμος [Seidel]. |
|
| εβδ.6
(13-16/11) |
Aυξητικός αλγόριθμος: αναμενόμενη πολυπλοκότητα. | |
| εβδ.7
Γειτνίαση (20-23/11) |
Διάγραμμα Voronoi σημείων. Tαυτότητα του Euler. Kάτω φράγμα, είδη αλγορίθμων.
Aυξητικός αλγόριθμος. Kατηγόρημα InCircle. |
Πρόοδος προπτυχιακών
(λύσεις)
και
μεταπτυχιακών
(λύσεις).
Παράδοση 20/11/06.
-- Κώδικας Java για Voronoi. |
| εβδ. 8
(27-30/11) |
Τριγωνοποίηση Delaunay, εφαρμογές. Nόμιμη τριγωνοποίηση, αντιστροφή ακμής. Αναγωγή σε ΚΠ3. Αυξητικός αλγόριθμος, μέση πολυπλοκότητα. | Δε. 27/11: Eπίλυση προόδου. |
| εβδ.9-10
(4/12-14/12) |
Διάγραμμα Voronoi κύκλων / ελλείψεων. Κανονικές τριγωνοποιήσεις. Φύλαξη μουσείου (Art Gallery). | Δε 4/12: φροντιστήριο
-- Εργασία 2. Παράδοση Δε 18/12 (email). |
| εβδ.11
(18-21/12) |
Σχήματα Άλφα (α-shapes). | Παρουσιάσεις άρθρων από τους μεταπτυχιακούς. |
| εβδ.12
(9/1/07-11/1) Διατάξεις |
Τομή και διατάξεις ευθυγράμμων τμημάτων στο επίπεδο. Κάτω φράγμα. Αλγόριθμος Bentley-Ottmann. | |
| εβδ.13
(16/1/07-18/1) |
Διατάξεις ευθειών: Αυξητικός αλγόριθμος, Θεώρημα ζώνης. | Τελική εξέταση (στο σπίτι) προπτυχιακών (λύσεις) και μεταπτυχιακών (λύσεις). Παράδοση όταν ολοκληρωθούν τα μαθήματα. |
| Παρουσιάσεις απαλλακτικών
Προπτυχιακών & Μεταπτυχιακών |
ΑΞΙΟΛΟΓΗΣΗ |
Σημειώσεις / Συγγράμματα
Σημειώσεις στα ελληνικά: geom.pdf
, geom.ps.gz
Προαιρετικά άρθρα