ΤΕΧΝΙΚΕΣ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΥΠΟΛΟΓΙΣΜΟΥ ΓΕΩΜΕΤΡΙΚΩΝ ΤΟΜΩΝ

Περίληψη

ΣΕ ΕΝΑ ΠΡΟΒΛΗΜΑ ΥΠΟΛΟΓΙΣΜΟΥ ΤΟΜΩΝ ΕΝΔΙΑΦΕΡΟΜΑΣΤΕ ΝΑ ΥΠΟΛΟΓΙΣΟΥΜΕ ΓΙΑ ΕΝΑ ΣΥΝΟΛΟ ΓΕΩΜΕΤΡΙΚΩΝ ΑΝΤΙΚΕΙΜΕΝΩΝ ΟΛΑ ΤΑ ΖΕΥΓΗ ΤΕΜΝΟΜΕΝΩΝ ΑΝΤΙΚΕΙΜΕΝΩΝ ΣΥΜΦΩΝΑ ΜΕ ΚΑΠΟΙΟ ΚΡΙΤΗΡΙΟ ΤΟΜΗΣ. ΣΕ ΑΥΤΗ ΤΗΝ ΔΙΑΤΡΙΒΗ ΕΞΕΤΑΖΟΥΜΕ ΠΡΟΒΛΗΜΑΤΑ ΤΟΜΩΝ ΚΑΙ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΗΝ ΑΠΟΔΟΤΙΚΟΤΕΡΗ ΕΠΙΛΥΣΗ ΤΟΥΣ. ΣΥΓΚΕΚΡΙΜΕΝΑ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΔΥΟ ΤΕΧΝΙΚΕΣ ΟΙ ΟΠΟΙΕΣ ΜΕΙΩΝΟΥΝ ΤΙΣ ΑΠΑΙΤΗΣΕΙΣ ΣΕ ΑΠΟΘΗΚΕΥΤΙΚΟ ΧΩΡΟ ΓΝΩΣΤΩΝ ΑΛΓΟΡΙΘΜΩΝ. ΟΙ ΛΥΣΕΙΣ ΠΟΥ ΠΡΟΚΥΠΤΟΥΝ ΑΠΑΙΤΟΥΝ ΒΕΛΤΙΣΤΟ ΑΠΟΘΗΚΕΥΤΙΚΟ ΧΩΡΟ O(N) ΒΕΛΤΙΩΝΟΝΤΑΣ ΠΡΟΗΓΟΥΜΕΝΕΣ ΛΥΣΕΙΣ. ΕΠΙΣΗΣ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΜΙΑ ΓΕΝΙΚΗ ΜΕΘΟΔΟ ΥΠΟΛΟΓΙΣΜΟΥ ΤΟΜΩΝ ΓΙΑ ΑΝΤΙΚΕΙΜΕΝΑ ΤΑ ΟΠΟΙΑ ΔΕΝ ΕΧΟΥΝ ΦΡΑΓΜΕΝΟ ΜΕΓΕΘΟΣ ΠΕΤΥΧΑΙΝΟΝΤΑΣ ΛΥΣΕΙΣ ΟΙ ΟΠΟΙΕΣ ΕΙΝΑΙ ΕΥΑΙΣΘΗΤΕΣ ΣΤΗΝ ΕΞΟΔΟ. ΤΕΛΟΣ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΜΙΑ ΛΥΣΗ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΣΗΜΕΙΩΝ ΜΕ ΑΚΕΡΑΙΕΣ ΣΥΝΤΕΤΑΓΜΕΝΕΣ. ΤΑ ΠΡΟΒΛΗΜΑΤΑ ΤΑ ΟΠΟΙΑ ΕΞΕΤΑΖΟΥΜΕ ΠΕΡΙΛΑΜΒΑΝΟΥΝ ΠΡΟΒΛΗΜΑΤΑ ΕΞΑΛΕΙΨΗΣ ΚΡΥΜΜΕΝΩΝ ΓΡΑΜΜΩΝ ΚΑΙ ΕΠΙΦΑΝΕΙΩΝ, ΠΡΟΒΛΗΜΑΤΑ ΤΟΜΩΝ ΕΥΘΥΓΡΑΜΜΩΝ ΤΜΗΜΑΤΩΝ ΚΑΙ ΠΡΟΒΛΗΜΑΤΑ ΤΟΜΩΝ ΟΡΘΟΓΩΝΙΩΝ. ΤΑ ΠΡΩΤΑ ΕΙΝΑΙ ΘΕΜΕΛΙΩΔΗ ΣΤΗΝ ΠΕΡΙΟΧΗ ΤΩΝ ΓΡΑΦΙΚΩΝ ΕΝ ...
περισσότερα

Περίληψη σε άλλη γλώσσα

IN AN INTERSECTION REPORTING PROBLEM WE ARE GIVEN A SET OF GEOMETRIC OBJECTS AND WE ARE ASKED TO DETERMINE ALL INTERSECTING PAIRS OF OBJECTS ACCORDING TO AN INTERSECTION CRITERION. IN THIS THESIS WE PRESENT TECHNIQUES WHICH EFFICIENTLY SOLVE KNOWN INTERSECTION PROBLEMS. OUR RESULTS INCLUDE TWO TECHNIQUES WHICH REDUCE THE STORAGE REQUIREMENTS OF SOME KNOWN ALGORITHMS. USING THESE TECHNIQUES WE ACHIEVE OPTIMAL STORAGE O(N) IMPROVING UPON PREVIOUS BOUNDS. WE ALSO PRESENT A GENERAL INTERSECTION REPORTING METHOD FOR OBJECTS OF NON - CONSTANT SIZE, WHICH YIELDS OUTPUT SENSITIVE RUNNING TIMES. FINALLY WE DEAL WITHPOINT DOMINANCE PROBLEMS FOR POINTS WITH INTEGER COORDINATES. THE PROBLEMS WE DEAL WITH INCLUDE HIDDEN LINE/SURFACE ELIMINATION, COMPUTATION OF LINE SEGMENT INTERSECTIONS AND COMPUTATION OF RECTANGLE ENCLOSURES. THE FORMER IS A FUNDAMENTAL PROBLEM IN COMPUTER GRAPHICS WHILE THE LATTER TWO HAVE APPLICATIONS IN VLSI DESIGN.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/8681
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/8681
Εναλλακτικός τίτλος
TECHNIQUES FOR GEOMETRIC INTERSECTION PROBLEMS
Συγγραφέας
ΚΙΤΣΙΟΣ, ΝΕΚΤΑΡΙΟΣ
Ημερομηνία
1997
Ίδρυμα
Πανεπιστήμιο Πατρών. Σχολή Πολυτεχνική. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Εξεταστική επιτροπή
ΤΣΑΚΑΛΙΔΗΣ ΑΘΑΝΑΣΙΟΣ
ΠΑΠΑΘΕΟΔΩΡΟΥ ΘΕΟΔΩΡΟΣ
ΣΠΥΡΑΚΗΣ ΠΑΥΛΟΣ
ΚΥΡΟΥΣΗΣ ΕΛΕΥΘΕΡΙΟΣ
ΓΑΛΛΟΠΟΥΛΟΣ ΕΥΣΤΡΑΤΙΟΣ
ΓΑΡΟΦΑΛΛΑΚΗΣ ΙΩΑΝΝΗΣ
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Μηχανική & Τεχνολογία
Επιστήμες Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού & Μηχανικού Η/Υ
Λέξεις-κλειδιά
Δομές δεδομένων; ΕΞΑΛΕΙΨΗ ΚΡΥΜΜΕΝΩΝ ΓΡΑΜΜΩΝ; ΜΕΙΩΣΗ ΧΩΡΟΥ; ΤΟΜΕΣ ΟΡΘΟΓΩΝΙΩΝ; ΤΟΜΕΣ ΧΡΩΜΑΤΩΝ; Υπολογιστική γεωμετρία
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά