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

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

Στην υπολογιστική γεωμετρία, η θεωρία πολυπλοκότητας χρησιμοποιείται εκτενώς για την ανάλυση του χρόνου εκτέλεσης (και της μνήμης) των αλγορίθμων, που έχει μεγάλη πρακτική σημασία ειδικά για πολύ μεγάλα σύνολα δεδομένων που μπορεί περιέχουν δεκάδες ή εκατοντάδες εκατομμύρια σημεία. Για τέτοια σύνολα με n σημεία, η διαφορά μεταξύ Θ(n2) και Θ(n log n) χρονικής πολυπλοκότητας μπορεί να είναι η διαφορά μεταξύ ημερών και δευτερολέπτων στην εκτέλεση του αλγορίθμου.

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

Άλλες σημαντικές εφαρμογές της υπολογιστικής γεωμετρίας περιλαμβάνουν τη ρομποτική (προβλήματα σχεδιασμού κίνησης και ορατότητας), συστήματα γεωγραφικών πληροφοριών (GIS) (γεωμετρική θέση και αναζήτηση, σχεδιασμός διαδρομής), σχεδιασμός ολοκληρωμένων κυκλωμάτων (σχεδιασμός και επαλήθευση γεωμετρίας IC), μηχανική με τη βοήθεια υπολογιστή (CAE) (δημιουργία πλεγμάτων) και μηχανική όραση (τρισδιάστατες ανακατασκευές).

Οι κύριοι κλάδοι της υπολογιστικής γεωμετρίας είναι οι εξής:

 Συνδυαστική υπολογιστική γεωμετρία, που ονομάζεται επίσης αλγοριθμική γεωμετρία, η οποία ασχολείται με τα γεωμετρικά αντικείμενα ως διακριτές οντότητες. Ένα βασικό βιβλίο για το θέμα από τους Preparata και Shamos κάνει την πρώτη χρήση του όρου «υπολογιστική γεωμετρία» με αυτή την έννοια το 1975. 
 Αριθμητική υπολογιστική γεωμετρία, που ονομάζεται επίσης γεωμετρία μηχανής, γεωμετρική σχεδίαση με τη βοήθεια υπολογιστή (CAGD) ή γεωμετρική μοντελοποίηση, η οποία ασχολείται κυρίως με την αναπαράσταση αντικειμένων του πραγματικού κόσμου σε μορφές κατάλληλες για υπολογισμούς υπολογιστών σε συστήματα CAD/CAM. Αυτός ο κλάδος μπορεί να θεωρηθεί ως μια περαιτέρω ανάπτυξη της περιγραφικής γεωμετρίας και συχνά θεωρείται κλάδος των γραφικών υπολογιστών ή του CAD. Ο όρος «υπολογιστική γεωμετρία» με αυτή την έννοια χρησιμοποιείται από το 1971.A.R. Forrest, "Computational geometry", Proc. Royal Society London, 321, series 4, 187-195 (1971)

Αν και οι περισσότεροι αλγόριθμοι υπολογιστικής γεωμετρίας έχουν αναπτυχθεί (και αναπτύσσονται) για ηλεκτρονικούς υπολογιστές, ορισμένοι αλγόριθμοι αναπτύχθηκαν για μη συμβατικούς υπολογιστές όπως οι οπτικοί υπολογιστές.

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


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

 Δίνονται n σημεία στο επίπεδο, βρείτε τα δύο με τη μικρότερη απόσταση μεταξύ τους.

Ένας τρόπος να λύσουμε αυτό το πρόβλημα είναι να υπολογίσουμε τις αποστάσεις μεταξύ όλων των ζευγαριών από σημεία, που είναι n(n-1)/2 στο πλήθος, και στη συνέχεια να επιλέξουμε το ζεύγος με τη μικρότερη απόσταση. Αυτός ο αλγόριθμος ωμής βίας χρειάζεται Θ(n2) χρόνο, δηλαδή ο χρόνος εκτέλεσής του είναι ανάλογος του τετραγώνου του αριθμού των σημείων. Ένα κλασικό αποτέλεσμα στην υπολογιστική γεωμετρία ήταν η διατύπωση ενός αλγορίθμου που χρειάζεται O(n log n). Επίσης έχουν διατυπωθεί πιθανοτικοί αλγόριθμοι που χρειάζονται O(n) αναμενόμενο χρόνο,S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995 (PDF) καθώς και ένας ντετερμινιστικός αλγόριθμος που χρειάζεται O(n log log n) χρόνοS. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979.

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

 Στατικά προβλήματα 
Στα προβλήματα αυτής της κατηγορίας μας δίνονται κάποια δεδομένα ως είσοδος και μας ζητείται να κατασκευάσουμε την αντίστοιχη έξοδο. Ορισμένα βασικά προβλήματα αυτού του τύπου είναι:

 Κυρτό περίβλημα: Για ένα δοσμένο συνόλου σημείων, βρείτε το μικρότερο κυρτό πολύεδρο/πολύγωνο που περιέχει όλα τα σημεία.
 Τομή ευθύγραμμων τμημάτων: Για ένα δοσμένο σύνολο ευθυγράμμων τμημάτων, βρείτε τις τομές μεταξύ τους.
 Τριγωνοποίηση Delaunay: Για ένα δοσμένο σύνολο σημείων, βρείτε την τριγωνοποίηση Delaynay.
 Διάγραμμα Voronoi: Για ένα δοσμένο σύνολο σημείων, χωρίστε το χώρο σύμφωνα με τα σημεία που βρίσκονται πιο κοντά στα δοσμένα σημεία.
 Γραμμικός προγραμματισμός
 Πλησιέστερο ζεύγος σημείων: Για ένα δοσμένο σύνολο σημείων, βρείτε τα δύο με τη μικρότερη απόσταση μεταξύ τους.
 Απομακρυσμένο ζεύγος σημείων: Αντίστοιχα και για το ζεύγος με τη μεγαλύτερη απόσταση μεταξύ τους.
 Μεγαλύτερος άδειος κύκλος: Για ένα δοσμένο σύνολο σημείων, βρείτε έναν κύκλο με την μεγαλύτερη ακτίνα με το κέντρο του μέσα στο κυρτό περίβλημα των σημείων και να μην περιέχει κανένα από αυτά.
 Ευκλείδεια συντομότερη διαδρομή: Συνδέστε δύο σημεία σε έναν Ευκλείδειο χώρο (με πολυεδρικά εμπόδια) με μια συντομότερη διαδρομή.
 Τριγωνοποίηση πολυγώνου: Για ένα δοσμένο πολύγωνο, χωρίστε το εσωτερικό του σε τρίγωνα.
 Δημιουργία πλεγμάτων
 Δυαδικές πράξεις σε πολύγωνα: Για δύο δοσμένα πολύγωνα, βρείτε την τομή, την ένωση ή την διαφορά τους.
 Έλεγχος σύγκρουσης: Για κάποια δοσμένα πολύγωνα/πολύεδρα, προσδιορίστε αν αυτά τέμνονται.

Η υπολογιστική πολυπλοκότητα για αυτήν την κατηγορία προβλημάτων εκτιμάται από τον χρόνο και τον χώρο (μνήμη υπολογιστή) που απαιτείται για την επίλυση ενός προβλήματος.

 Προβλήματα με γεωμετρικά ερωτήματα 

Στα προβλήματα γεωμετρικών ερωτημάτων, κοινώς γνωστά ως προβλήματα γεωμετρικής αναζήτησης, η είσοδος αποτελείται από δύο τμήματα: το τμήμα χώρου αναζήτησης και το τμήμα ερωτήματος, το οποίο ποικίλλει ανάλογα με τις περιπτώσεις προβλημάτων. Στόχος είναι να προεπεξεργαστούμε τον χώρο αναζήτησης, ώστε να μπορούμε να απαντήσουμε πολλαπλά ερωτήματα αποδοτικά.

Μερικά κλασσικά προβλήματα γεωμετρικών ερωτημάτων είναι τα εξής:

 Αναζήτηση ως προς ορθογώνια περιοχή: Προεπεξεργαστείτε ένα δοσμένο σύνολο σημείων, ώστε να μπορείτε αποδοτικά να μετρήσετε το πλήθος των σημείων μέσα στο διάστημα του ερωτήματος.
 Πρόβλημα εντοπισμού σημείου: Για έναν δοσμένο διαμερισμό του χώρου σε κελιά, δημιουργήστε μια δομή δεδομένων που απαντάει αποδοτικά σε ποιο κελί βρίσκεται το σημείο του ερωτήματος.
 Πλησιέστερος γείτονας: Προεπεξεργαστείτε ένα σύνολο σημείων, για να βρείτε αποτελεσματικά ποιο σημείο είναι πιο κοντά σε ένα σημείο ερωτήματος.
 Ιχνηλάτηση ακτίνων: Για ένα δοσμένο σύνολο αντικειμένων στο χώρο, δημιουργήστε μια δομή δεδομένων που απαντάει αποδοτικά ποιο αντικείμενο τέμνει πρώτο η ακτίνα του ερωτήματος.

Για έναν δοσμένο χώρο αναζήτησης, η υπολογιστική πολυπλοκότητα για αυτήν την κατηγορία προβλημάτων συνήθως εκτιμάται από:

 τον χρόνο και τον χώρο που απαιτούνται για την κατασκευή της δομής δεδομένων, η οποία θα χρησιμοποιείται για την απάντηση των ερωτημάτων
 τον χρόνο (και μερικές φορές τον επιπλέον χώρο) για την απάντηση του κάθε ερωτήματος.

Για την περίπτωση που ο χώρος αναζήτησης μπορεί να αλλάζει, ανατρέξτε στην ενότητα " Δυναμικά προβλήματα".

 Δυναμικά προβλήματα 
Μια άλλη σημαντική κατηγορία είναι τα δυναμικά προβλήματα, στα οποία ο στόχος είναι να βρεθεί ένας αποδοτικός αλγόριθμος για την εύρεση λύσης επανειλημμένα μετά από κάθε σταδιακή τροποποίηση των δεδομένων εισόδου (προσθήκη ή διαγραφή γεωμετρικών στοιχείων). Οι αλγόριθμοι για προβλήματα αυτού του τύπου συνήθως περιλαμβάνουν δυναμικές δομές δεδομένων. Οποιοδήποτε από τα υπολογιστικά γεωμετρικά προβλήματα μπορεί να μετατραπεί σε δυναμικό, τις περισσότερες φορές οδηγώντας σε αύξηση του χρόνου πολυπλοκότητας. Για παράδειγμα, το πρόβλημα αναζήτησης ως προς ορθογώνια περιοχή μπορεί να μετατραπεί στο πρόβλημα δυναμικής αναζήτησης ως προς ορθογώνια περιοχή αν επιτρέψουμε την προσθήκη ή/και διαγραφή κάποιων από τα σημεία. Το πρόβλημα του δυναμικού κυρτού περιβλήματος είναι ο εντοπισμός του κυρτού περιβλήματος, π.χ. για το δυναμικά μεταβαλλόμενο σύνολο σημείων, δηλαδή, καθώς κάποια από τα σημεία εισόδου προστίθενται ή διαγράφονται.

Για αυτήν την κατηγορία προβλημάτων εκτιμούμε την υπολογιστική πολυπλοκότητα για:

 τον χρόνο και τον χώρο που απαιτούνται για την κατασκευή της δομής δεδομένων
 τον χρόνο και τον χώρο για την τροποποίηση της δομής δεδομένων αναζήτησης μετά από μια σταδιακή αλλαγή στο χώρο αναζήτησης
 τον χρόνο (και μερικές φορές τον επιπλέον χώρο) για την απάντηση του κάθε ερωτήματος.

 Παραλλαγές 

Ορισμένα προβλήματα μπορεί να θεωρηθούν ότι ανήκουν σε οποιαδήποτε από τις κατηγορίες, ανάλογα με το πλαίσιο στο οποίο διατυπώνεται το πρόβλημα. Για παράδειγμα, εξετάστε το ακόλουθο πρόβλημα.

 Σημείο σε πολύγωνο : Αποφασίστε εάν ένα σημείο είναι εσωτερικό ή εξωτερικό ενός δοσμένου πολυγώνου.

Σε διάφορες εφαρμογές μπορεί να έχουμε μόνο ένα σημείο που θέλουμε να ελέγξουμε και έτσι το πρόβλημα ανήκει στην πρώτη κατηγορία. Για παράδειγμα, σε πολλές εφαρμογές γραφικών υπολογιστή ένα κοινό πρόβλημα είναι να βρείτε σε ποια περιοχή στην οθόνη γίνεται κλικ με το ποντίκι. Ωστόσο, σε ορισμένες εφαρμογές, το εν λόγω πολύγωνο μπορεί να είναι αμετάβλητο, και να υπάρχουν πολλά σημεία που πρέπει να ελέγξουμε. Για παράδειγμα, το πολύγωνο εισόδου μπορεί να αντιπροσωπεύει τα σύνορα μιας χώρας και ένα σημείο να είναι μια θέση ενός αεροσκάφους και το πρόβλημα είναι να προσδιοριστεί εάν το αεροσκάφος παραβίασε τα σύνορα. Σε αυτή την περίπτωση το πρόβλημα ανήκει στην δεύτερη κατηγορία. Τέλος, στο προαναφερθέν παράδειγμα στα γραφικά υπολογιστών, στις εφαρμογές CAD τα μεταβαλλόμενα δεδομένα εισόδου αποθηκεύονται συχνά σε δυναμικές δομές δεδομένων, οι οποίες μπορούν να αξιοποιηθούν για την γρηγορότερη απάντηση των ερωτημάτων.

Σε κάποια προβλήματα με ερωτήματα, μπορεί να πρέπει να γίνουν επιπλέον υποθέσεις για την σειρά των ερωτημάτων ώστε να αξιοποιηθούν αποδοτικές δομές δεδομένων ή να γίνουν καλύτερες εκτιμήσεις υπολογιστικής πολυπλοκότητας. Για παράδειγμα, κάποιες φορές μας ενδιαφέρει η συνολική χρονική πολυπλοκότητα για ολόκληρη την ακολουθία των N ερωτημάτων, αντί αυτή για το χειρότερο ερώτημα. Δείτε επίσης "επιμερισμένη ανάλυση".

 Αριθμητική υπολογιστική γεωμετρία 
Αυτός ο κλάδος είναι επίσης γνωστός ως γεωμετρική μοντελοποίηση και γεωμετρικός σχεδιασμός με τη βοήθεια υπολογιστή (CAGD).

Τα βασικά προβλήματα είναι η μοντελοποίηση και η αναπαράσταση καμπυλών και επιφανειών.

Τα πιο σημαντικά εργαλεία εδώ είναι οι παραμετρικές καμπύλες και οι παραμετρικές επιφάνειες, όπως οι καμπύλες Bézier, οι καμπύλες spline και οι επιφάνειες. Μια σημαντική μη παραμετρική προσέγγιση είναι η μέθοδος ισοϋψών .

Οι τομείς εφαρμογής της υπολογιστικής γεωμετρίας περιλαμβάνουν τη ναυπηγική, την αεροναυπηγική και την αυτοκινητοβιομηχανία.

 Περαιτέρω ανάγνωση 

 Εξωτερικοί σύνδεσμοι 
 Υπολογιστική Γεωμετρία
 Σελίδες Υπολογιστικής Γεωμετρίας
 Γεωμετρία σε δράση
 "Strategic Directions in Computational Geometry - Working Group Report" (1996)
 Journal of Computational Geometry
 (Ετήσια) Χειμερινή Σχολή Υπολογιστικής Γεωμετρίας
 Εργαστήριο Υπολογιστικής Γεωμετρίας

Μαθήματα/Διαλέξεις
 Υπολογιστική Γεωμετρία (ΑΠΘ), Τσίχλας Κωνσταντίνος
 Υπολογιστική Γεωμετρία (Πανεπιστήμιο Ιωαννίνων), Λεωνίδας Παληός
 Υπολογιστική Γεωμετρία (Πανεπιστήμιο Πελοποννήσου), Θεοχάρης Μαλαμάτος 
 Computational geometry (University of California), David Eppstein
 Computational geometry (University of Illinois), Jeff Erickson
 Computational geometry (MIT), N. Patrikalakis & T. Maekawa
 Computatinal Geometry (UC Berkeley), J. Shewchuk

 Περιοδικά 
Παρακάτω δίνεται μία λίστα από τα πιο σημαντικά περιοδικά στα οποία δημοσιεύεται έρευνα σε γεωμετρικούς αλγορίθμους. Παρατηρήστε ότι με την εμφάνιση περιοδικών ειδικευόμενων στην υπολογιστική γεωμετρία, το μερίδιο των γεωμετρικών δημοσιεύσεων σε περιοδικά γενικής χρήσης πληροφορικής και γραφικών υπολογιστών μειώθηκε.

 ACM Computing Surveys
 ACM Transactions on Graphics
 Acta Informatica
 Advances in Geometry
 Algorithmica
 Ars Combinatoria
 Computational Geometry: Theory and Applications
 Communications of the ACM
 Computer Aided Geometric Design
 Computer Graphics and Applications
 Computer Graphics World
 Computing in Geometry and Topology
 Discrete Computational Geometry
 Geombinatorics
 Geometriae Dedicata
 IEEE Transactions on Graphics
 IEEE Transactions on Computers
 IEEE Transactions on Pattern Analysis and Machine Intelligence
 Information Processing Letters
 International Journal of Computational Geometry and Applications
 Journal of Combinatorial Theory, Series B
 Journal of Computational Geometry
 Journal of Differential Geometry
 Journal of the ACM
 Journal of Algorithms
 Journal of Computer and System Sciences
 Management Science
 Pattern Recognition
 Pattern Recognition Letters
 SIAM Journal on Computing
 SIGACT News, το οποίο είχε μία στήλη αφιερωμένη υπολογιστική γεωμετρία γραμμένη από τον Joseph O'Rourke
 Theoretical Computer Science
 The Visual Computer

 Παραπομπές 

 Εξωτερικοί σύνδεσμοι