Υπολογιστική Γεωμετρία

Διδάσκων: Θεοχάρης Μαλαμάτος

Διαλέξεις: Πέμπτη 3-5μμ, Αίθουσα Ι11 και Παρασκευή 1-3μμ, Αίθουσα Ι13



Περιγραφή

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


Περιεχόμενα

A/A

Ενότητα

1

Εισαγωγή

2

Κυρτό Περίβλημα

3

Τομές Ευθύγραμμων Τμημάτων

4

Τριγωνοποίηση Πολύγωνου

5

Τομή Ημιεπιπέδων

6

Δυισμός και Κάτω Περιβάλλουσα

7

Αναζήτηση Ορθογώνιας Περιοχής: kd-Δέντρα, Δέντρα Περιοχής

8

Εντοπισμός Σημείου

9

Διαγράμματα Voronoi

10

Τριγωνοποιήσεις Delaunay

11

Διατάξεις Ευθειών

12

Γραμμικός Προγραμματισμός

13

Κυρτά Περιβλήματα και Διαγράμματα Voronoi

14

Περισσότερες Γεωμετρικές Δομές Δεδομένων

15

Γραφήματα Ορατότητας


Βιβλία και Σημειώσεις

Τα δωρεάν συγγράμματα για το μάθημα είναι τα εξής:

Τα παραπάνω βιβλία υπάρχουν στη βιβλιοθήκη της σχολής μαζί επίσης με τα εξής βιβλία υπολογιστικής γεωμετρίας:

Οι σημειώσεις του διδάσκοντα παρέχονται στην πλατφόρμα eclass.


Βαθμολογία

Οι ασκήσεις συνεισφέρουν 50% του βαθμού ενώ το υπόλοιπο ποσοστό προέρχεται από το βαθμό στην τελική γραπτή εξέταση.


Ασκήσεις

Κατά τη διάρκεια του εξαμήνου θα δοθούν μία σειρά από ατομικές ασκήσεις. Τα θέματα των ασκήσεων θα τοποθετούνται στην πλατφόρμα eclass. Η ημερομηνία παράδοσης της κάθε άσκησης θα ανακοινώνεται στο μάθημα και στο eclass.