Πολυδιάστατες Δομές Δεδομένων

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

• Η ύλη του μαθήματος στοχεύει στην εισαγωγή των φοιτητών στις βασικές έννοιες των πολυδιάστατων δομών δεδομένων όπως: το δένδρο διαστημάτων (Interval Tree), το δένδρο Προτεραιότητας (Priority Search Tree), το δένδρο ευθυγράμμων τμημάτων (Segment Tree), το δένδρο περιοχής (Range-tree), το δέντρο ορθογωνίων (R- tree), το τετραδικό δέντρο (Quad-Tree), το k-διάστατο δέντρο (kd-tree) και στις εφαρμογές αυτών σε προβλήματα υπολογιστικής γεωμετρίας και γραφικών όπως: Αναπαράσταση Ευθειών και κόμβων (σημείων) στο Raster Display, ο βασικός incremental αλγόριθμος, O αλγόριθμος του Bresenham για ευθείες, ο αλγόριθμος του Bresenham για κύκλους, 2-διάστατοι μετασχηματισμοί, Παράθυρο και αποκοπής- αλγόριθμοι, segment- clipping αλγόριθμοι, Aποκοπή πολυγώνων, Mετασχηματισμοί όψης, το πρόβλημα συνολικού εμβαδού απλών πολυγώνων, Διαγραφή μη ορατών γραμμών (Hidden line elimination problem), Τομή ευθυγράμμων τμημάτων, Τριγωνοποίηση πολυγώνων, Γραμμικός προγραμματισμός στη γεωμετρία, Αναζήτηση περιοχής (orthogonal range), Εντοπισμός σημείων, Διαγράμματα Voronoi, Τριγωνοποίηση Delaunay, Γεωμετρικές δομές, Κυρτό περίβλημα, Δυαδικές χωρικές διαμερίσεις, Γράφοι ορατότητας. Με την επιτυχή ολοκλήρωση του μαθήματος ο/η φοιτητής/τρια θα είναι σε θέση να:

• Έχει κατανοήσει τις βασικές έννοιες των πολυδιάστατων δομών δεδομένων.

• Υλοποιεί και να διαχειρίζεται τις βασικές πολυδιάστατες δομές δεδομένων.
• Έχει κατανοήσει τα βασικά εργαλεία ανάλυσης και σχεδίασης αλγορίθμων με έμφαση στην υπολογιστική γεωμετρία.
• Επιλέγει την κατάλληλη πολυδιάστατη δομή δεδομένων για την επίλυση του προβλήματος υπολογιστικής γεωμετρίας που αντιμετωπίζει.

Περιεχόμενο (ύλη)

1η εβδομάδα: Aλγοριθμική Γεωμετρία: Eισαγωγή, Oρθογώνια στοιχεία, Tο δένδρο διαστημάτων (Δ.Δ.), H planesweep τεχνική, Mια εφαρμογή του Δ.Δ. 2η εβδομάδα: Tο δένδρο Προτεραιότητας (Δ.Π.), Σταθερό Σύμπαν, Eλεύθερο Σύμπαν, Eφαρμογές του Δ.Π. 3η εβδομάδα: Tο δένδρο ευθυγράμμων τμημάτων (Δ.E.T.), Σταθερό Σύμπαν, Eλεύθερο Σύμπαν, Mια εφαρμογή του Δ.E.T. 4η εβδομάδα: Tο δένδρο περιοχής (Range-tree), Fractional Cascading 5η εβδομάδα: Το δέντρο ορθογωνίων (R-tree), το τετραδικό δέντρο (Quad-Tree), το k-διάστατο δέντρο (kd-tree) 6η εβδομάδα: Kατάτμηση του επιπέδου σε μονοπάτια και Sweep-line τεχνική για μη ορθοκανονικά αντικείμενα. Tο πρόβλημα συνολικού εμβαδού απλών πολυγώνων. Διαγραφή μη ορατών γραμμών (Hidden line elimination problem) 7η εβδομάδα: Αναπαράσταση Ευθειών και κόμβων (σημείων) στο Raster Display, ο βασικός incremental αλγόριθμος, ο αλγόριθμος του Bresenham για ευθείες, ο αλγόριθμος του Bresenham για κύκλους, 2-διάστατοι μετασχηματισμοί, παράθυρο και αποκοπής- αλγόριθμοι, segment-clipping αλγόριθμοι, αποκοπή πολυγώνων, μετασχηματισμοί όψης 8η εβδομάδα: Τομή ευθυγράμμων τμημάτων και Τριγωνοποίηση πολυγώνων 9η εβδομάδα:. Γραμμικός προγραμματισμός στη γεωμετρία 10η εβδομάδα:. Αναζήτηση περιοχής (orthogonal range) και Εντοπισμός σημείων 11η εβδομάδα: Διαγράμματα Voronoi, Τριγωνοποίηση Delaunay

12η εβδομάδα: Γεωμετρικές δομές, Κυρτό περίβλημα 13η εβδομάδα: Δυαδικές χωρικές διαμερίσεις, Γράφοι ορατότητας

Αξιολόγηση

1. Διαλέξεις
2. Ασκήσεις Πράξης που εστιάζουν στην εφαρμογή μεθοδολογιών και ανάλυση μελετών περίπτωσης σε μικρότερες ομάδες φοιτητών
3. Υποστήριξη εργασίας
4. Γραπτή Εξέταση με Ερωτήσεις Σύντομης Απάντησης (Διαμορφωτική, Συμπερασματική)
5. Γραπτή Εξέταση με Επίλυση Προβλημάτων (Συμπερασματική)

Βιβλιογραφία

Συνιστώμενη βιβλιογραφία προς μελέτη:

1. “Προχωρημένες Δομές δεδομένων και Computer-Γραφική”, Α. Κ. Τσακαλίδης, Εκδόσεις Πανεπιστημίου Πατρών, 2010.
2. “ Υπολογιστική Γεωμετρία – Αλγόριθμοι και Εφαρμογές», De Berg Mark, Cheong Otfried, Van Krevel

Marc, Overmars Mark, Ίδρυμα Τεχνολογίας & Έρευνας – Πανεπιστημιακές Εκδόσεις Κρήτης, 2011. 3. Υπολογιστική Γεωμετρία: Μια Σύγχρονη Προσέγγιση, Γιάννης Ζ. Εμίρης, Εκδόσεις Κλειδάριθμος ΕΠΕ, 2008. Επιπρόσθετη βιβλιογραφία για μελέτη:

1. 1. J. O'Rourke, Computational Geometry in C, Cambridge University Press, 2nd edition, 1998.
2. 1. F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction, Springer, New York,
3. 1. Handbook of Discrete and Computational geometry.