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

Abstract

ΣΕ ΕΝΑ ΠΡΟΒΛΗΜΑ ΥΠΟΛΟΓΙΣΜΟΥ ΤΟΜΩΝ ΕΝΔΙΑΦΕΡΟΜΑΣΤΕ ΝΑ ΥΠΟΛΟΓΙΣΟΥΜΕ ΓΙΑ ΕΝΑ ΣΥΝΟΛΟ ΓΕΩΜΕΤΡΙΚΩΝ ΑΝΤΙΚΕΙΜΕΝΩΝ ΟΛΑ ΤΑ ΖΕΥΓΗ ΤΕΜΝΟΜΕΝΩΝ ΑΝΤΙΚΕΙΜΕΝΩΝ ΣΥΜΦΩΝΑ ΜΕ ΚΑΠΟΙΟ ΚΡΙΤΗΡΙΟ ΤΟΜΗΣ. ΣΕ ΑΥΤΗ ΤΗΝ ΔΙΑΤΡΙΒΗ ΕΞΕΤΑΖΟΥΜΕ ΠΡΟΒΛΗΜΑΤΑ ΤΟΜΩΝ ΚΑΙ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΤΕΧΝΙΚΕΣ ΓΙΑ ΤΗΝ ΑΠΟΔΟΤΙΚΟΤΕΡΗ ΕΠΙΛΥΣΗ ΤΟΥΣ. ΣΥΓΚΕΚΡΙΜΕΝΑ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΔΥΟ ΤΕΧΝΙΚΕΣ ΟΙ ΟΠΟΙΕΣ ΜΕΙΩΝΟΥΝ ΤΙΣ ΑΠΑΙΤΗΣΕΙΣ ΣΕ ΑΠΟΘΗΚΕΥΤΙΚΟ ΧΩΡΟ ΓΝΩΣΤΩΝ ΑΛΓΟΡΙΘΜΩΝ. ΟΙ ΛΥΣΕΙΣ ΠΟΥ ΠΡΟΚΥΠΤΟΥΝ ΑΠΑΙΤΟΥΝ ΒΕΛΤΙΣΤΟ ΑΠΟΘΗΚΕΥΤΙΚΟ ΧΩΡΟ O(N) ΒΕΛΤΙΩΝΟΝΤΑΣ ΠΡΟΗΓΟΥΜΕΝΕΣ ΛΥΣΕΙΣ. ΕΠΙΣΗΣ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΜΙΑ ΓΕΝΙΚΗ ΜΕΘΟΔΟ ΥΠΟΛΟΓΙΣΜΟΥ ΤΟΜΩΝ ΓΙΑ ΑΝΤΙΚΕΙΜΕΝΑ ΤΑ ΟΠΟΙΑ ΔΕΝ ΕΧΟΥΝ ΦΡΑΓΜΕΝΟ ΜΕΓΕΘΟΣ ΠΕΤΥΧΑΙΝΟΝΤΑΣ ΛΥΣΕΙΣ ΟΙ ΟΠΟΙΕΣ ΕΙΝΑΙ ΕΥΑΙΣΘΗΤΕΣ ΣΤΗΝ ΕΞΟΔΟ. ΤΕΛΟΣ ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΜΙΑ ΛΥΣΗ ΓΙΑ ΠΡΟΒΛΗΜΑΤΑ ΣΗΜΕΙΩΝ ΜΕ ΑΚΕΡΑΙΕΣ ΣΥΝΤΕΤΑΓΜΕΝΕΣ. ΤΑ ΠΡΟΒΛΗΜΑΤΑ ΤΑ ΟΠΟΙΑ ΕΞΕΤΑΖΟΥΜΕ ΠΕΡΙΛΑΜΒΑΝΟΥΝ ΠΡΟΒΛΗΜΑΤΑ ΕΞΑΛΕΙΨΗΣ ΚΡΥΜΜΕΝΩΝ ΓΡΑΜΜΩΝ ΚΑΙ ΕΠΙΦΑΝΕΙΩΝ, ΠΡΟΒΛΗΜΑΤΑ ΤΟΜΩΝ ΕΥΘΥΓΡΑΜΜΩΝ ΤΜΗΜΑΤΩΝ ΚΑΙ ΠΡΟΒΛΗΜΑΤΑ ΤΟΜΩΝ ΟΡΘΟΓΩΝΙΩΝ. ΤΑ ΠΡΩΤΑ ΕΙΝΑΙ ΘΕΜΕΛΙΩΔΗ ΣΤΗΝ ΠΕΡΙΟΧΗ ΤΩΝ ΓΡΑΦΙΚΩΝ ΕΝΩ ΤΑ ΥΠΟΛΟΙΠΑ ΕΧΟΥΝ ΠΟΛΛΕΣ ΕΦΑΡΜΟΓΕΣ ΣΤΗΝ ΣΧΕΔΙΑΣΗ VLSI.

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.