Υπολογιστική Γεωμετρία
Κωδ.:
ΘΠ11
Εξάμηνο:
8
Τύπος μαθήματος νέο ΠΠΣ
:
Προαιρετικά Μαθήματα (ΠΜ)
K (new pps):
A
E1:
B
E2:
E
Ώρες Θεωρίας:
3
Ώρες Φροντιστηρίου:
1
Προαπαιτούμενα Μαθήματα:
Κατεύθυνση:
Θεωρητική Πληροφορική
Κυρτό περίβλημα σημείων σε 2, 3 και περισσότερες διαστάσεις, αλγόριθμος περιτύλιξης, μέθοδος διαίρει και βασίλευε, αυξητικός αλγόριθμος και υπολογισμός όγκου πολυέδρου. Πολυπλοκότητα χείριστης περίπτωσης και ευαίσθητη εξόδου, κάτω φράγματα, θεώρημα άνω φράγματος στο μέγεθος κυρτών περιβλημάτων, γεωμετρικός δυϊσμός. Γραμμική βελτιστοποίηση, αλγόριθμος Simplex, τυχαιοκρατικοί αλγόριθμοι και αναμενόμενη πολυπλοκότητα. Διάγραμμα Voronoi, μέθοδος σάρωσης, τριγωνοποίηση Delaunay, σύνδεση με το κυρτό περίβλημα. Τριγωνοποίηση σημειοσυνόλου σε 2 και περισσότερες διαστάσεις, τριγωνοποίηση απλού πολυγώνου και φύλαξη μουσείου, προβλήματα ορατότητας στο επίπεδο. Κάθετη υποδιαίρεση, εντοπισμός σημείου, πλησιέστερος γείτονας, γεωμετρικές δομές δεδομένων και γεωμετρική αναζήτηση. Διατάξεις ευθυγράμμων τμημάτων και ευθειών. Προβλήματα υλοποίησης, εκφυλισμένα δεδομένα και διαταραχή της εισόδου. Εφαρμογές στον σχεδιασμό της κίνησης ρομπότ, στη μελέτη της δομής μακρομορίων, στην γεωμετρική σχεδίαση με υπολογιστή (CAD) και στα γραφικά. Υλοποίηση γεωμετρικών αλγορίθμων στην βιβλιοθήκη γεωμετρικού λογισμικού CGAL ή σε Python.