Το πρόβλημα της ελάχιστης κάλυψης ορθογωνίου πολυγώνου με s-αστέρες
| dc.contributor.author | Γορδίου, Ειρήνη | el |
| dc.date.accessioned | 2021-11-09T11:58:47Z | |
| dc.date.available | 2021-11-09T11:58:47Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/31468 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.11289 | |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | ς-αστέρας | el |
| dc.subject | Ορθογώνιο πολύγωνο | el |
| dc.subject | Ελάχιστη κάλυψη | el |
| dc.subject | ς-ορατότητα | el |
| dc.subject | s-stars | en |
| dc.subject | Orthogonal polygon | en |
| dc.subject | Minimum cover | en |
| dc.subject | s-visible | en |
| dc.title | Το πρόβλημα της ελάχιστης κάλυψης ορθογωνίου πολυγώνου με s-αστέρες | el |
| dc.title | The problem of covering orthogonal polygons with the minimum number of s-stars | en |
| heal.abstract | Ένα πολύγωνο στο επίπεδο λέγεται ορθογώνιο εάν κάθε ακμή του είναι είτε οριζόντια είτε κατακόρυφη. Δύο σημεία ενός ορθογωνίου πολυγώνου P είναι s-ορατά το ένα από το άλλο εάν μπορούν να συνδεθούν εντός του P με μία κλιμακοειδή διαδρομή, δηλαδή μια μονότονη διαδρομή με εναλλάξ οριζόντια και κατακόρυφα τμήματα (μια τέτοια διαδρομή αν ξεκινήσει με κατεύθυνση προς τα δεξιά και άνω συνεχίζει προς τα δεξιά και άνω έως το τέλος της). Τότε ένα ορθογώνιο πολύγωνο Q λέγεται s-αστέρας αν υπάρχει σημείο του από το οποίο κάθε άλλο σημείο του Q είναι s-ορατό. Τέλος, μια συλλογή S από πολύγωνα αποτελεί κάλυμμα ενός πολυγώνου R αν κάθε σημείο του R ανήκει σε κάποιο πολύγωνο στη συλλογή S (δηλαδή το R ανήκει πλήρως στην ένωση των πολυγώνων στη συλλογή S). Στην παρούσα μεταπτυχιακή εργασία μελετήσαμε και υλοποιήσαμε τον αλγόριθμο των Motwani, Raghunathan και Saran για τον υπολογισμό ενός καλύμματος ενός γενικού ορθογωνίου πολυγώνου (χωρίς οπές) από το ελάχιστο πλήθος s-αστέρων. Ο αλγόριθμος συνδυάζει ιδιότητες ορατότητας με αποτελέσματα Θεωρίας Γραφημάτων και έχει πολυπλοκότητα χρόνου 𝑂(n^8) όπου 𝑛 είναι το πλήθος κορυ-φών του δοθέντος ορθογωνίου πολυγώνου. Επιπλέον, παρουσιάζουμε έναν αλγόριθμο για την κατασκευή «τυχαίων» ορθογωνίων πολυγώνων εντός δοθέντος ορθογωνίου παραλληλογράμμου με βάση δοθέντα συντελεστή «πυκνότητας». Η υλοποίηση των αλγορίθμων πραγματοποιήθηκε στη γλώσσα προγραμματι-σμού C++, ενώ η οπτικοποίηση των πολυγώνων με βιβλιοθήκες της OpenGL. | el |
| heal.abstract | 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. | en |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Παληός, Λεωνίδας | el |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 96-97 | el |
| heal.classification | Αλγόριθμοι υπολογιστών | |
| heal.committeeMemberName | Παληός, Λεωνίδας | el |
| heal.committeeMemberName | Γεωργιάδης, Λουκάς | el |
| heal.committeeMemberName | Νομικός, Χρήστος | el |
| heal.dateAvailable | 2021-11-09T11:59:47Z | |
| heal.fullTextAvailability | true | |
| heal.language | el | |
| heal.numberOfPages | 98 σ. | |
| heal.publicationDate | 2021 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΓΟΡΔΙΟΥ ΕΙΡΗΝΗ 2021.pdf
- Μέγεθος:
- 2.75 MB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: