Εθνικό Καποδιστριακό Πανεπιστημίο Αθηνών - Τμήμα Πληροφορικής & Tηλεπικοινωνιών
Χειμερινό Εξάμηνο 2007

ΥΠΟΛΟΓΙΣΤΙΚΗ ΓΕΩΜΕΤΡΙΑ

Aίθουσα Γ' (Πληροφορικής), Πέμπτη 11-1, Παρασκ. 12-2 μμ.
Διδάσκoντες: Γιάννης Eμίρης, Χριστόδουλος Φραγκουδάκης

Δείτε τις απαλλακτικές που εκπονήθηκαν στα πλαίσια του μαθήματος
Πρόγραμμα
Εβδομάδα
Διαλέξεις
Διάφορα
εβδ.1.
Εισαγωγή
(18-19/10)		 Τι είναι η Υπολογιστική Γεωμετρία; Σύνδεση με τα γραφικά, την δομική μοριακή βιολογία, με μαθήματα θεωρητικής πληροφορικής. Υπολογιστικό μοντέλο.
--
Κυρτό περίβλημα σε 2 διάστασεις (ΚΠ2). Aλγόριθμος τυλίγματος δώρου (gift-wrapping). Κατηγόρημα αριστερής στροφής CCW (counter-clockwise) για 3 σημεία.		 Οδηγίες εγκατάστασης για CGAL και CGAL-Python. Python για την CGAL. Eισαγωγή στην Python.

Μια εισαγωγή στην CGAL βρίσκεται εδώ. Κλάσεις / templates C++.
εβδ.2
Κυρτότητα 		 Αυξητικός αλγόριθμος (Βeneath-beyond), επέκταση στο ΚΠ3. Φράγματα στην Πολυπλοκότητα. 
Εργασία 0.
Παράδοση
Δευτ. 5/11.
Λύση, Βαθμοί.
εβδ.3
1-2/11		 Πολύεδρα, έδρες. ΚΠ3: αυξητικός αλγόριθμος. Κατηγόρημα προσανατολισμού. Διαταραχή σημείων.
--
Μη κυρτά πολύγωνα, τριγωνοποίηση απλού πολυγώνου.
 Demos (παλαιότερες εργασίες): Περιτύλιγμα, Αλγόριθμος KS.
Κυρτά περιβλήματα (demos).
Κώδικας Java για Voronoi.
εβδ.4
8-9/11
 Προβλήματα υλοποίησης, εκφυλισμένα δεδομένα. Πολυπλοκότητα. Θεώρημα McMullen. Αλγόριθμος τυλίγματος δώρου (gift-wrapping) σε 3 διαστάσεις. Άσκηση 1, παράδοση Δ.19/11.
Προπτυχιακού+λύσεις. Μεταπτυχιακού+λύσεις. Βαθμοί.
εβδ.5
22-23/11		 Eπίλυση ασκήσεων 1.
--
Ανάλυση τυλίγματος δώρου σε 3 διαστάσεις. Δυϊσμός (ισοδυναμία άΠ2 με Tομή ημιεπιπέδων). Γραμμική Bελτιστοποίηση.
εβδ.6
29-30/11
Ορατότητα		 Πρόβλημα φύλαξης και Θεώρημα του μουσείου (Art Gallery Problem, Theorem). Τοποθέτηση ⌊n/3⌋ φυλάκων μέσω Τριγωνοποίησης. Απόδειξη NP-hardness για το πρόβλημα της ελαχιστοποίησης του αριθμού των φυλάκων. Προβλήματα μεγιστοποίησης της φύλαξης με δεδομένο αριθμό φυλάκων (προσεγγιστικές λύσεις). Εργασία 1
Παράδοση Δευτ. 10/12
Λύση, Βαθμοί.
εβδ.7
6-7/12
Διαμερίσεις που διακριτοποιούν την ορατότητα από τις κορυφές και τις ακμές του πολυγώνου. Σύνδεση με προβλήματα μεγιστοποίησης της κάλυψης. Αναφορά στη δομή Doubly Connected Edge List. Διαμέριση απλού πολυγώνου σε μονότονα πολύγωνα. Τριγωνοποίηση μονότονου Πολυγώνου.
 
εβδ. 8
13-14/12
Γειτνίαση
 Διάγραμμα Voronoi σημείων. Tαυτότητα του Euler. Kάτω φράγμα, είδη αλγορίθμων. Αναγωγή σε ΚΠ3. Aυξητικός αλγόριθμος. Kατηγόρημα InCircle. Τριγωνοποίηση Delaunay.
εβδ.9
20-21/12
 Τριγωνοποίηση Delaunay, κανονικες τριγωνοποιήσεις. Αναγωγή σε ΚΠ3. Αυξητικός αλγόριθμος: Nόμιμη τριγωνοποίηση, αντιστροφή ακμής, μέση πολυπλοκότητα.   Προγραμ. Εργασία 2, παράδοση Τ. 9/1/08.
Λύση, Βαθμοί.
εβδ.10
10-11/1
 Εφαρμογές τριγωνοποιήσεων, σχήματα Άλφα (α-shapes) για την περιγραφή πολύπλοκων αντικειμένων. Ορισμοί και ιδιότητες: α-σύνορο, α-σύμπλοκο, α-σχήμα.
Άσκηση 2, παράδοση T.16/1/08.
Προπτυχιακού (λύση). Μεταπτυχιακού (λύση).
Βαθμοί.

εβδ.11
17-18/1
Γεωμετρική αναζήτηση		 Yπολογισμός α-σχημάτων.
---
Δομές στην ευθεία, kd-δένδρα στο επίπεδο.
Επιλογή  απαλλακτικής.

Eπιλογή άρθρου.
εβδ.12
24-25/1
 Δομές γεωμετρικών δεδομένων στο επίπεδο: kd-δένδρα, δένδρα περιοχής.
Παρουσιάσεις άρθρων IA.
----
Παρουσιάσεις απαλλακτικών. 		Άσκηση 3 (bonus), παράδοση T.30/1/08.
Προπτυχιακού. Μεταπτυχιακού.
Λύσεις,  Βαθμοί

ΑΞΙΟΛΟΓΗΣΗ
Tελικοί βαθμοί
Βαθμολογία

Περίπου 1/3 για καθένα από τα εξής:
- 3 Προγραμματιστικές εργασίες CGAL-Python, ή Παρουσίαση και περίληψη άρθρων,
- Δύο θεωρητικές ασκήσεις στο σπίτι,
- Γραπτή εξέταση, ή Προγραμματιστική απαλλακτική εργασία.

Υποστήριξη

email:
Γιάννης Eμίρης (emiris at di...),
Χριστόδουλος Φραγκουδάκης (chfrag AT di...)
Bοηθός: Γιώργος Τζούμας (geotz at di...).

Σημειώσεις (ελληνικά): geom.pdf , geom.ps.gz

Bιβλία που μπορείτε να δανειστείτε από την βιβλιοθήκη ή τον διδάσκοντα:
Διαδίκτυο
"Oρίζοντας" 3d πόλης, ως σύνθεση 2d οριζόντων, σε CGAL [Φ. Πάσχος, 2006]

I.Z.Eμίρης