Υπολογιστική Γεωμετρία
Ακ. Έτος 2015-2016

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Γενικές Πληροφορίες

Διδάσκων:

Τσίχλας Κωνσταντίνος

Email - URL - Τηλ.:

tsichlas@delab.csd.auth.gr - http://delab.csd.auth.gr/~tsichlas/ - 2310991934

Ώρες Διαλέξεων:

Τρίτη 9-12 Αίθουσα Γ

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Περιγραφή

Η υπολογιστική γεωμετρία είναι η περιοχή της επιστήμης της Πληροφορικής που αφορά τη μελέτη αλγορίθμων σχετικά με γεωμετρικά προβλήματα. Η ώθηση σε αυτό το πεδίο δόθηκε από την ανάπτυξη άλλων περιοχών, όπως η υπολογιστική γραφική, ρομποτική, γεωγραφικά συστήματα πληροφοριών, υπολογιστικά βοηθούμενη σχεδίαση κ.α. Ο κυρίαρχος στόχος είναι η ανάπτυξη αποδοτικών αλγορίθμων και δομών δεδομένων για την επίλυση προβλημάτων σε γεωμετρικά αντικείμενα όπως σημεία, ευθείες, πολύγωνα κτλ.

Αξιολόγηση Μαθήματος

Θα περιλαμβάνει μία τελική εξέταση καθώς και προγραμματιστικές/θεωρητικές εργασίες. Στην τελική εξέταση μπορείτε να έχετε μαζί σας μία κόλλα Α4 με ό,τι θέλετε σε αυτή (μπρος-πίσω).

 Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Ανακοινώσεις

1. Εδώ θα βρείτε ένα σύνολο ασκήσεων που αφορά όλα τα κεφάλαια που θα γίνουν (καλό είναι να προσπαθείτε κάθε άσκηση αφού η αντίστοιχη ύλη έχει γίνει στο μάθημα). Προσοχή, ο βαθμός της εργασίας είναι προσθετικός (αυτό σημαίνει ότι προστίθεται αυτούσιος στο βαθμό της εξέτασης)

2. Το μάθημα της Τρίτης στις 10/5 δεν θα γίνει και θα μεταφερθεί την Πέμπτη 12/5, ώρα 17-20, στην αίθουσα  Β.

3. Η καταλήκτικη ημερομήνια παράδοσης για την εργασία είναι Παρασκευή 27/6/2016.

4. Το μάθημα της Τρίτης στις 31/5 θα γίνει κανονικά (δεν θα μεταφερθεί όπως συζητήθηκε στο μάθημα). Το μάθημα θα ξεκινήσεις στις 10:00.

5. Εδώ θα βρείτε την βαθμολογία των γραπτών και εδώ θα βρείτε τα θέματα με τις ενδεικτικές λύσεις τους. Όποιος θέλει να δει το γραπτό του να επικοινωνήσει με τον διδάσκοντα μέσω email. (ΕΝΗΜΕΡΩΣΗ 26/6/2016) Η απάντηση των ενδεικτικών λύσεων στο ερώτημα 6(β) είναι λάθος: Αυτό γιατί δεν θέλουμε ένα σημείο ταυτόχρονα και στα 2n ημιεπίπεδα αλλά σε n από αυτά. Η σωστή λύση είναι να χρησιμοποιήσουμε διπλοσυνδεδεμένο κατάλογο ακμών και να αποθηκεύουμε αυτές τις μη κυρτές περιοχές (σφήνες) με στόχο να βρούμε την τομή τους. Αν αυτή είναι μη κενή τότε είμαστε ΟΚ. Συνολικός χρόνος Ο(n2logn) - είναι πιο δύσκολο από την αρχική μου εκτίμηση και ως εκ τούτου δεν αλλάζει η βαθμολόγηση των γραπτών. Αυτό μειώνεται σε O(n2) αν εκμεταλλευτούμε την κυρτότηα.

6. ΝΕΟ!!! Εδώ θα βρείτε τους τελικούς βαθμούς μαζί με τους βαθμούς των ασκήσεων.

Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Ημερολόγιο Μαθήματος

Διάλεξη

Ημερομηνία

Ύλη Εβδομάδας

Υλικό

1η

16/2/2016

Εισαγωγή, Το Πρόβλημα του Κυρτού Περιβλήματος ([1] Σελ. 1-16)

Διαφάνειες

2η

23/2/2016

Τομές Ευθυγράμμων Τμημάτων ([1], Σελ. 19-29)

Διαφάνειες

 

1/3/2016

Δεν γίνεται μάθημα λόγω απουσίας του διδάσκοντα στο εξωτερικό.

3η

8/3/2016

Εισαγωγή στο Πρόβλημα Τριγωνισμού Πολυγώνου

Διαφάνειες

 

15/3/2016

Δεν γίνονται μαθήματα στο Α.Π.Θ.

4η

22/3/2016

Ορθογώνια Εκτασιακή Αναζήτηση (Κεφάλαιο 5)

Διαφάνειες

5η

29/3/2016

Τριγωνισμός Πολυγώνου (Κεφάλαιο 3)

 

6η

5/4/2016

Κεφάλαιο 5 (συνέχεια): Fractional Cascading (μόνο για τον σκοπό των Layered Range Trees), Layered Range Trees, Degenerate Cases

Κεφάλαιο 10: Interval Trees, Priority Search Trees

Διαφάνειες 43-66 από http://www.cs.uu.nl/docs/vakken/ga/slides5b.pdf
Διαφάνειες 1-73 από http://www.cs.uu.nl/docs/vakken/ga/slides10.pdf

7η

12/4/2016

Κεφάλαιο 10 (συνέχεια): Segment Trees (έγινε 1 ώρα από τις τρεις)

Διαφάνειες, σελ. 19-27

8η

19/4/2016

Κεφάλαιο 6: Point Location

Διαφάνειες από http://www.cs.uu.nl/docs/vakken/ga/slides6.pdf

9η

12/5/2016

Κεφάλαιο 4: Γραμμικός Προγραμαμτισμός

Διαφάνειες

10η

17/5/2016

Κεφάλαιο 7: Διαγράμματα Voronoi. Διαφάνειες 4-8, 19-77 

Διαφάνειες από http://www.cs.uu.nl/docs/vakken/ga/slides7.pdf

11η

24/5/2017

Κέφάλαιο 4 (Συνέχεια)

Δες διαλέξεις 12/5

12η

31/5/2016

Κεφάλαιο 8 (τα 8.3 και 8.4 είναι εκτός)

Διαφάνειες

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό

Χρήσιμο Υλικό

Τα βασικά εγχειρίδια του μαθήματος είναι:

  1. Υπολογιστική Γεωμετρία: Αλγόριθμοι και Εφαρμογές. Mark de Berg, Marc van Kreveld, Mark Overmars και Otfried Cheong. Πανεπιστημιακές Εκδόσεις Κρήτης 2011.

  2. Υπολογιστική Γεωμετρία: μία σύγχρονη αλγοριθμική προσέγγιση. Γιάννης Ζ. Εμίρης. Εκδόσεις Κλειδάριθμος, 2008.

Τα ακόλουθα βιβλία και ιστότοποι είναι αρκετά χρήσιμοι για το μάθημα.

  1. Computational Geometry in C. J. O'Rourke. Cambridge University Press (2nd edition), 1998.

  2. Computational Geometry: An Introduction. F.P. Preparata and M. Shamos. Monographs in Computer Science, Springer, 1993.

Γενικές Πληροφορίες    Περιγραφή    Ανακοινώσεις    Ημερολόγιο    Χρήσιμο Υλικό