Dissertation/ Thesis
Το πρόβλημα της ελάχιστης κάλυψης ορθογωνίου πολυγώνου με s-αστέρες ; The problem of covering orthogonal polygons with the minimum number of s-stars
| العنوان: | Το πρόβλημα της ελάχιστης κάλυψης ορθογωνίου πολυγώνου με s-αστέρες ; The problem of covering orthogonal polygons with the minimum number of s-stars |
|---|---|
| المؤلفون: | Γορδίου, Ειρήνη |
| المساهمون: | Παληός, Λεωνίδας, Γεωργιάδης, Λουκάς, Νομικός, Χρήστος |
| بيانات النشر: | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής uoi |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | ς-αστέρας, Ορθογώνιο πολύγωνο, Ελάχιστη κάλυψη, ς-ορατότητα, s-stars, Orthogonal polygon, Minimum cover, s-visible, Αλγόριθμοι υπολογιστών |
| الوصف: | Ένα πολύγωνο στο επίπεδο λέγεται ορθογώνιο εάν κάθε ακμή του είναι είτε οριζόντια είτε κατακόρυφη. Δύο σημεία ενός ορθογωνίου πολυγώνου 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 ... |
| نوع الوثيقة: | master thesis |
| اللغة: | Greek, Modern (1453-) |
| Relation: | https://olympias.lib.uoi.gr/jspui/handle/123456789/31468; http://dx.doi.org/10.26268/heal.uoi.11289; Βιβλιογραφία: σ. 96-97 |
| DOI: | 10.26268/heal.uoi.11289 |
| الاتاحة: | https://olympias.lib.uoi.gr/jspui/handle/123456789/31468 https://doi.org/10.26268/heal.uoi.11289 |
| Rights: | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ ; Attribution-NonCommercial-NoDerivs 3.0 United States ; free |
| رقم الانضمام: | edsbas.13789A61 |
| قاعدة البيانات: | BASE |
| DOI: | 10.26268/heal.uoi.11289 |
|---|