Το πρόβλημα της ελάχιστης κάλυψης ορθογωνίου πολυγώνου με s-αστέρες
Φόρτωση...
Ημερομηνία
Συγγραφείς
Γορδίου, Ειρήνη
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Ένα πολύγωνο στο επίπεδο λέγεται ορθογώνιο εάν κάθε ακμή του είναι είτε οριζόντια είτε κατακόρυφη. Δύο σημεία ενός ορθογωνίου πολυγώνου P είναι s-ορατά το ένα από το άλλο εάν μπορούν να συνδεθούν εντός του P με μία κλιμακοειδή διαδρομή, δηλαδή μια μονότονη διαδρομή με εναλλάξ οριζόντια και κατακόρυφα τμήματα (μια τέτοια διαδρομή αν ξεκινήσει με κατεύθυνση προς τα δεξιά και άνω συνεχίζει προς τα δεξιά και άνω έως το τέλος της). Τότε ένα ορθογώνιο πολύγωνο Q λέγεται s-αστέρας αν υπάρχει σημείο του από το οποίο κάθε άλλο σημείο του Q είναι s-ορατό. Τέλος, μια συλλογή S από πολύγωνα αποτελεί κάλυμμα ενός πολυγώνου R αν κάθε σημείο του R ανήκει σε κάποιο πολύγωνο στη συλλογή S (δηλαδή το R ανήκει πλήρως στην ένωση των πολυγώνων στη συλλογή S). Στην παρούσα μεταπτυχιακή εργασία μελετήσαμε και υλοποιήσαμε τον αλγόριθμο των Motwani, Raghunathan και Saran για τον υπολογισμό ενός καλύμματος ενός γενικού ορθογωνίου πολυγώνου (χωρίς οπές) από το ελάχιστο πλήθος s-αστέρων. Ο αλγόριθμος συνδυάζει ιδιότητες ορατότητας με αποτελέσματα Θεωρίας Γραφημάτων και έχει πολυπλοκότητα χρόνου 𝑂(n^8) όπου 𝑛 είναι το πλήθος κορυ-φών του δοθέντος ορθογωνίου πολυγώνου. Επιπλέον, παρουσιάζουμε έναν αλγόριθμο για την κατασκευή «τυχαίων» ορθογωνίων πολυγώνων εντός δοθέντος ορθογωνίου παραλληλογράμμου με βάση δοθέντα συντελεστή «πυκνότητας». Η υλοποίηση των αλγορίθμων πραγματοποιήθηκε στη γλώσσα προγραμματι-σμού C++, ενώ η οπτικοποίηση των πολυγώνων με βιβλιοθήκες της OpenGL.
A polygon in a plane is called orthogonal if each of its edges is either horizontal or vertical. Two points of an orthogonal polygon are s-visible from each other if they can be connected within P by a staircase path, i.e. a monotone path with alternating horizontal and vertical line segments (such a path if it starts in a right and upward direction keeps proceeding right and upwards until its end). Then an orthogonal polygon Q is called s-star if there is a point from which every other point of Q is s-visible. Finally, a set S of polygons is the cover of a polygon R if every point on R belongs to a polygon in S (i.e. R belongs entirely to the union of the polygons in S). In the present Master's thesis we study and implement the algorithm of Motwani, Raghunathan and Saran to compute a cover of a simple orthogonal polygon (without holes) consisting of the minimum number of s-stars. The algorithm combines visibility properties with Graph Theory results and has (n^8) time complexity where 𝑛 is the number of vertices of the given orthogonal polygon. In addition, we present an algorithm for constructing "random" orthogonal polygons within a given rectangle based on a given "density" coefficient. The algorithms have been implemented in the C++ programming language, while the polygons have been visualized with OpenGL libraries.
A polygon in a plane is called orthogonal if each of its edges is either horizontal or vertical. Two points of an orthogonal polygon are s-visible from each other if they can be connected within P by a staircase path, i.e. a monotone path with alternating horizontal and vertical line segments (such a path if it starts in a right and upward direction keeps proceeding right and upwards until its end). Then an orthogonal polygon Q is called s-star if there is a point from which every other point of Q is s-visible. Finally, a set S of polygons is the cover of a polygon R if every point on R belongs to a polygon in S (i.e. R belongs entirely to the union of the polygons in S). In the present Master's thesis we study and implement the algorithm of Motwani, Raghunathan and Saran to compute a cover of a simple orthogonal polygon (without holes) consisting of the minimum number of s-stars. The algorithm combines visibility properties with Graph Theory results and has (n^8) time complexity where 𝑛 is the number of vertices of the given orthogonal polygon. In addition, we present an algorithm for constructing "random" orthogonal polygons within a given rectangle based on a given "density" coefficient. The algorithms have been implemented in the C++ programming language, while the polygons have been visualized with OpenGL libraries.
Περιγραφή
Λέξεις-κλειδιά
ς-αστέρας, Ορθογώνιο πολύγωνο, Ελάχιστη κάλυψη, ς-ορατότητα, s-stars, Orthogonal polygon, Minimum cover, s-visible
Θεματική κατηγορία
Αλγόριθμοι υπολογιστών
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Όνομα επιβλέποντος
Παληός, Λεωνίδας
Εξεταστική επιτροπή
Παληός, Λεωνίδας
Γεωργιάδης, Λουκάς
Νομικός, Χρήστος
Γεωργιάδης, Λουκάς
Νομικός, Χρήστος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 96-97
Ονόματα συντελεστών
Αριθμός σελίδων
98 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States