.
Η υπολογιστική γεωμετρία είναι ένας κλάδος της επιστήμης των υπολογιστών που είναι αφιερωμένος στη μελέτη αλγορίθμων που μπορούν να δηλωθούν με όρους γεωμετρίας. Μερικά καθαρά γεωμετρικά προβλήματα προκύπτουν από τη μελέτη υπολογιστικών γεωμετρικών αλγορίθμων και τέτοια προβλήματα θεωρούνται επίσης μέρος της υπολογιστικής γεωμετρίας. Ενώ η σύγχρονη υπολογιστική γεωμετρία είναι μια πρόσφατη εξέλιξη, είναι ένα από τα παλαιότερα πεδία της πληροφορικής με ιστορία που εκτείνεται από την αρχαιότητα.
Η υπολογιστική πολυπλοκότητα είναι κεντρική στην υπολογιστική γεωμετρία, με μεγάλη πρακτική σημασία εάν χρησιμοποιούνται αλγόριθμοι σε πολύ μεγάλα σύνολα δεδομένων που περιέχουν δεκάδες ή εκατοντάδες εκατομμύρια σημεία. Για τέτοια σύνολα, η διαφορά μεταξύ O(n) και O(n log n) μπορεί να είναι η διαφορά μεταξύ ημερών και δευτερολέπτων υπολογισμού.
Η κύρια ώθηση για την ανάπτυξη της υπολογιστικής γεωμετρίας ως κλάδου ήταν η πρόοδος στα γραφικά υπολογιστών και στον σχεδιασμό και την κατασκευή με τη βοήθεια υπολογιστή (CAD/CAM), αλλά πολλά προβλήματα στην υπολογιστική γεωμετρία είναι κλασικής φύσης και μπορεί να προέρχονται από μαθηματική απεικόνιση.
Άλλες σημαντικές εφαρμογές της υπολογιστικής γεωμετρίας περιλαμβάνουν τη ρομποτική (προβλήματα σχεδιασμού κίνησης και ορατότητας), συστήματα γεωγραφικών πληροφοριών (GIS) (γεωμετρική θέση και αναζήτηση, σχεδιασμός διαδρομής), σχεδιασμός ολοκληρωμένων κυκλωμάτων (σχεδιασμός και επαλήθευση γεωμετρίας IC), μηχανική με τη βοήθεια υπολογιστή (CAE) (δημιουργία πλέγματος), και όραση υπολογιστή (3D ανακατασκευή).
Οι κύριοι κλάδοι της υπολογιστικής γεωμετρίας είναι:
Συνδυαστική υπολογιστική γεωμετρία, που ονομάζεται επίσης αλγοριθμική γεωμετρία, η οποία ασχολείται με τα γεωμετρικά αντικείμενα ως διακριτές οντότητες. Ένα βιβλίο θεμελιώδους βάσης για το θέμα από τους Preparata και Shamos χρονολογεί την πρώτη χρήση του όρου «υπολογιστική γεωμετρία» με αυτή την έννοια το 1975.[1]
Αριθμητική υπολογιστική γεωμετρία, που ονομάζεται επίσης γεωμετρία μηχανής, γεωμετρική σχεδίαση με τη βοήθεια υπολογιστή (CAGD) ή γεωμετρική μοντελοποίηση, η οποία ασχολείται κυρίως με την αναπαράσταση αντικειμένων του πραγματικού κόσμου σε μορφές κατάλληλες για υπολογισμούς υπολογιστών σε συστήματα CAD/CAM. Αυτός ο κλάδος μπορεί να θεωρηθεί ως μια περαιτέρω ανάπτυξη της περιγραφικής γεωμετρίας και συχνά θεωρείται κλάδος των γραφικών υπολογιστών ή του CAD. Ο όρος «υπολογιστική γεωμετρία» με αυτή την έννοια χρησιμοποιείται από το 1971.[2]
Αν και οι περισσότεροι αλγόριθμοι υπολογιστικής γεωμετρίας έχουν αναπτυχθεί (και αναπτύσσονται) για ηλεκτρονικούς υπολογιστές, ορισμένοι αλγόριθμοι αναπτύχθηκαν για μη συμβατικούς υπολογιστές (π.χ. οπτικοί υπολογιστές [3]).
Συνδυαστική υπολογιστική γεωμετρία
Ο πρωταρχικός στόχος της έρευνας στη συνδυαστική υπολογιστική γεωμετρία είναι η ανάπτυξη αποτελεσματικών αλγορίθμων και δομών δεδομένων για την επίλυση προβλημάτων που αναφέρονται σε βασικά γεωμετρικά αντικείμενα: σημεία, ευθύγραμμα τμήματα, πολύγωνα, πολύεδρα κ.λπ.
Μερικά από αυτά τα προβλήματα φαίνονται τόσο απλά που δεν θεωρούνταν καθόλου προβλήματα μέχρι την εμφάνιση των υπολογιστών. Εξετάστε, για παράδειγμα, το πρόβλημα του πλησιέστερου ζεύγους:
Δεδομένων n σημείων στο επίπεδο, βρείτε τα δύο με τη μικρότερη απόσταση μεταξύ τους.
Θα μπορούσε κανείς να υπολογίσει τις αποστάσεις μεταξύ όλων των ζευγών σημείων, από τα οποία είναι n(n-1)/2, και στη συνέχεια να επιλέξει το ζεύγος με τη μικρότερη απόσταση. Αυτός ο αλγόριθμος ωμής δύναμης απαιτεί χρόνο O(n2). δηλ. Ο χρόνος εκτέλεσής του είναι ανάλογος του τετραγώνου του αριθμού των σημείων. Ένα κλασικό αποτέλεσμα στην υπολογιστική γεωμετρία ήταν η διατύπωση ενός αλγορίθμου που παίρνει O(n log n). Τυχαιοποιημένοι αλγόριθμοι που χρειάζονται O(n) αναμενόμενο χρόνο,[4] καθώς και ένας ντετερμινιστικός αλγόριθμος που απαιτεί χρόνο O(n log log n)[5] έχουν επίσης ανακαλυφθεί.
Προβληματικές τάξεις
Τα βασικά προβλήματα στην υπολογιστική γεωμετρία μπορούν να ταξινομηθούν με διαφορετικούς τρόπους, σύμφωνα με διάφορα κριτήρια. Μπορούν να διακριθούν οι ακόλουθες γενικές κατηγορίες.
Στατικά προβλήματα
Στα προβλήματα αυτής της κατηγορίας δίνεται κάποια είσοδος και χρειάζεται να κατασκευαστεί ή να βρεθεί η αντίστοιχη έξοδος. Ορισμένα βασικά προβλήματα αυτού του τύπου είναι:
Κυρτό περίβλημα: Δεδομένου ενός συνόλου σημείων, βρείτε το μικρότερο κυρτό πολύεδρο/πολύγωνο που περιέχει όλα τα σημεία.
Τομή ευθύγραμμου τμήματος: Βρείτε τις τομές μεταξύ ενός δεδομένου συνόλου ευθύγραμμων τμημάτων.
Τριγωνισμός Delaunay
Διάγραμμα Voronoi: Δεδομένου ενός συνόλου σημείων, χωρίστε τον χώρο σύμφωνα με τα σημεία που βρίσκονται πιο κοντά στα δεδομένα που δίνονται.
Γραμμικός προγραμματισμός
Πλησιέστερο ζεύγος σημείων: Δεδομένου ενός συνόλου σημείων, βρείτε τα δύο με τη μικρότερη απόσταση μεταξύ τους.
Το πιο μακρινό ζευγάρι πόντων
Μεγαλύτερος κενός κύκλος: Δεδομένου ενός συνόλου σημείων, βρείτε έναν μεγαλύτερο κύκλο με το κέντρο του μέσα στο κυρτό κύτος τους και να μην περικλείει κανένα από αυτά.
Ευκλείδεια συντομότερη διαδρομή: Συνδέστε δύο σημεία σε έναν Ευκλείδειο χώρο (με πολυεδρικά εμπόδια) με μια συντομότερη διαδρομή.
Τριγωνισμός πολυγώνου: Δίνεται ένα πολύγωνο, χωρίστε το εσωτερικό του σε τρίγωνα
γενιά πλέγματος
Πράξεις Boolean σε πολύγωνα
Η υπολογιστική πολυπλοκότητα για αυτήν την κατηγορία προβλημάτων εκτιμάται από τον χρόνο και τον χώρο (μνήμη υπολογιστή) που απαιτείται για την επίλυση ενός δεδομένου στιγμιότυπου προβλήματος.
Προβλήματα γεωμετρικών ερωτημάτων
Στα προβλήματα γεωμετρικών ερωτημάτων, κοινώς γνωστά ως προβλήματα γεωμετρικής αναζήτησης, η είσοδος αποτελείται από δύο μέρη: το τμήμα χώρου αναζήτησης και το τμήμα ερωτήματος, το οποίο ποικίλλει ανάλογα με τις περιπτώσεις προβλημάτων. Ο χώρος αναζήτησης συνήθως χρειάζεται να υποβληθεί σε προεπεξεργασία, με τρόπο ώστε να μπορούν να απαντηθούν αποτελεσματικά πολλαπλά ερωτήματα.
Μερικά θεμελιώδη γεωμετρικά προβλήματα ερωτημάτων είναι:
Αναζήτηση εύρους: Προεπεξεργαστείτε ένα σύνολο σημείων, προκειμένου να μετρήσετε αποτελεσματικά τον αριθμό των σημείων μέσα σε μια περιοχή ερωτήματος.
Θέση σημείου: Δεδομένου ενός διαμερίσματος του χώρου σε κελιά, δημιουργήστε μια δομή δεδομένων που λέει αποτελεσματικά σε ποιο κελί βρίσκεται ένα σημείο ερωτήματος.
Πλησιέστερος γείτονας: Προεπεξεργαστείτε ένα σύνολο σημείων, για να βρείτε αποτελεσματικά ποιο σημείο είναι πιο κοντά σε ένα σημείο ερωτήματος.
Ανίχνευση ακτίνων: Δεδομένου ενός συνόλου αντικειμένων στο χώρο, δημιουργήστε μια δομή δεδομένων που λέει αποτελεσματικά ποιο αντικείμενο τέμνει πρώτο μια ακτίνα ερωτήματος.
Εάν ο χώρος αναζήτησης διορθωθεί, η υπολογιστική πολυπλοκότητα για αυτήν την κατηγορία προβλημάτων συνήθως εκτιμάται από:
ο χρόνος και ο χώρος που απαιτούνται για την κατασκευή της δομής δεδομένων προς αναζήτηση
ο χρόνος (και μερικές φορές ένας επιπλέον χώρος) για να απαντήσετε σε ερωτήματα.
Για την περίπτωση που ο χώρος αναζήτησης επιτρέπεται να ποικίλλει, ανατρέξτε στην ενότητα "Δυναμικά προβλήματα".
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
