1 Υπολογιστική γεωμετρία
Εισαγωγή
1.1 Ένα παράδειγμα: κυρτά περιβλήματα
1.2 Εκφυλισμένες περιπτώσεις και ευστάθεια
1.3 Πεδία εφαρμογών
1.4 Σημειώσεις και σχόλια
1.5 Ασκήσεις
2 Τομή ευθύγραμμων τμημάτων
Υπέρθεση θεματικών χαρτών
2.1 Τομή ευθύγραμμων τμημάτων
2.2 Ο διπλοσυνδεδεμένος κατάλογος ακμών
2.3 Υπολογισμός της υπέρθεσης δύο υποδιαιρέσεων
2.4 Λογικές πράξεις
2.5 Σημειώσεις και σχόλια
2.6 Ασκήσεις
3 Τριγωνισμός πολυγώνου
Επιτήρηση πινακοθήκης
3.1 Επιτήρηση και τριγωνισμοί
3.2 Διαμέριση πολυγώνου σε μονότονα τεμάχια
3.3 Τριγωνισμός μονότονου πολυγώνου
3.4 Σημειώσεις και σχόλια
3.5 Ασκήσεις
4 Γραμμικός προγραμματισμός
Βιομηχανική παραγωγή με μήτρες
4.1 Η γεωμετρική ανάλυση της χύτευσης
4.2 Τομή ημιεπιπέδων
4.3 Αυξητικός γραμμικός προγραμματισμός
4.4 Τυχαιοκρατικός γραμμικός προγραμματισμός
4.5 Μη φραγμένα γραμμικά προγράμματα
4.6* Γραμμικός προγραμματισμός σε περισσότερες διαστάσεις
4.7* Μικρότατοι περικλείοντες δίσκοι
4.8 Σημειώσεις και σχόλια
4.9 Ασκήσεις
5 Ορθογωνική εκτασιακή αναζήτηση
Ερωτήματα προς βάσεις δεδομένων
5.1 Μονοδιάστατη εκτασιακή αναζήτηση
5.2 kd-δέντρα
5.3 Εκτασιακά δέντρα
5.4 Εκτασιακά δέντρα περισσότερων διαστάσεων
5.5 Τυχόντα σύνολα σημείων
5.6* Κλασματική επαλληλία
5.7 Σημειώσεις και σχόλια
5.8 Ασκήσεις
6 Εντοπισμός σημείου
Πώς ξέρουμε πού βρισκόμαστε
6.1 Εντοπισμός σημείου και τραπεζιομερείς χάρτες
6.2 Ένας τυχαιοκρατικός αυξητικός αλγόριθμος
6.3 Αντιμετώπιση των εκφυλισμένων περιπτώσεων
6.4* Μια εκτίμηση για την ουρά της κατανομής
6.5 Σημειώσεις και σχόλια
6.6 Ασκήσεις
7 Διαγράμματα Voronoi
Το πρόβλημα του ταχυδρομείου
7.1 Ορισμός και βασικές ιδιότητες
7.2 Υπολογισμός του διαγράμματος Voronoi
7.3 Διαγράμματα Voronoi ευθύγραμμων τμημάτων
7.4 Διαγράμματα Voronoi απώτατων σημείων
7.5 Σημειώσεις και σχόλια
7.6 Ασκήσεις
8 Σχηματισμοί και δυϊκότητα
Υπερδειγματοληψία κατά την ακτινηλάτηση
8.1 Υπολογισμός της απόκλισης
8.2 Δυϊκότητα
8.3 Σχηματισμοί ευθειών
8.4 Βαθμίδες και απόκλιση
8.5 Σημειώσεις και σχόλια
8.6 Ασκήσεις
9 Τριγωνισμοί Delaunay
Παρεμβολή καθ’ ύψος
9.1 Τριγωνισμοί επίπεδων σημειοσυνόλων
9.2 Ο τριγωνισμός Delaunay
9.3 Υπολογισμός του τριγωνισμού Delaunay
9.4 Ανάλυση
9.5* Ένα πλαίσιο για τυχαιοκρατικούς αλγορίθμους
9.6 Σημειώσεις και σχόλια
9.7 Ασκήσεις
10 Άλλες γεωμετρικές δομές δεδομένων
Παραθυρική εστίαση
10.1 Δέντρα διαστημάτων
10.2 Προτεραϊκά δέντρα αναζήτησης
10.3 Δέντρα ευθύγραμμων τμημάτων
10.4 Σημειώσεις και σχόλια
10.5 Ασκήσεις
11 Κυρτά περιβλήματα
Μείξεις
11.1 Η πολυπλοκότητα των κυρτών περιβλημάτων στον τριδιάστατο χώρο
11.2 Υπολογισμός κυρτών περιβλημάτων στον τριδιάστατο χώρο
11.3* Ανάλυση
11.4* Κυρτά περιβλήματα και τομή ημιχώρων
11.5* Επανεξέταση των διαγραμμάτων Voronoi
11.6 Σημειώσεις και σχόλια
11.7 Ασκήσεις
12 Δυαδικές διαμερίσεις χώρου
Ο αλγόριθμος του ζωγράφου
12.1 Ορισμός των δέντρων ΔΔΧ
12.2 Δέντρα ΔΔΧ και ο αλγόριθμος του ζωγράφου
12.3 Κατασκευή δέντρου ΔΔΧ
12.4* Το μέγεθος των δέντρων ΔΔΧ στον τριδιάστατο χώρο
12.5 Δέντρα ΔΔΧ για σκηνές χαμηλής πυκνότητας
12.6 Σημειώσεις και σχόλια
12.7 Ασκήσεις
13 Σχεδιασμός κίνησης ρομπότ
Μετάβαση στο επιθυμητό σημείο
13.1 Χώρος εργασίας και χώρος διαμορφώσεων
13.2 Ένα σημειακό ρομπότ
13.3 Αθροίσματα Minkowski
13.4 Σχεδιασμός μετατοπιστικής κίνησης
13.5* Σχεδιασμός κίνησης με περιστροφές
13.6 Σημειώσεις και σχόλια
13.7 Ασκήσεις
14 Τετραδικά δέντρα
Κατασκευή ανομοιόμορφου πλέγματος
14.1 Ομοιόμορφα και ανομοιόμορφα πλέγματα
14.2 Τετραδικά δέντρα για σημειοσύνολα
14.3 Από τα τετραδικά δέντρα στα πλέγματα
14.4 Σημειώσεις και σχόλια
14.5 Ασκήσεις
15 Γραφήματα ορατότητας
Εύρεση βραχύτατης διαδρομής
15.1 Βραχύτατες διαδρομές για σημειακό ρομπότ
15.2 Υπολογισμός του γραφήματος ορατότητας
15.3 Βραχύτατες διαδρομές για μετατοπιζόμενο πολυγωνικό ρομπότ
15.4 Σημειώσεις και σχόλια
15.5 Ασκήσεις
16 Απλοκοειδής εκτασιακή αναζήτηση
Επανεξέταση της παραθυρικής εστίασης
16.1 Διαμεριστικά δέντρα
16.2 Πολυβαθμιδικά διαμεριστικά δέντρα
16.3 Κοπτικά δέντρα
16.4 Σημειώσεις και σχόλια
16.5 Ασκήσεις
Λεξικό βασικών όρων
Βιβλιογραφία
Ευρετήριο
