ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ SITE MAP | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΕΛΛΗΝΙΚΑ | ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ENGLISH
Παρασκευή, 21/11/2014   -   Ομιλίες
Σεμινάριο Τμήματος με τίτλο:Κάλυψη ορθογωνίων πολυγώνων τύπου 3 με το ελάχιστο πλήθος r-αστέρων
Σεμινάριο Τμήματος

Στο πλαίσιο της διοργάνωσης εβδομαδιαίων σεμιναρίων του τμήματος διοργανώνεται η πέμπτη διάλεξη, η οποία θα πραγματοποιηθεί την Παρασκευή 21/11/2014 και ώρα 12:00 στην αίθουσα Σεμιναρίων του Τμήματος Μηχανικών Η/Υ και Πληροφορικής. Ομιλητής θα είναι ο κ. Λεωνίδας Παληός, Αναπληρωτής Καθηγητής Τμήματος Μηχανικών Η/Υ & Πληροφορικής, και o τίτλος της διάλεξης είναι «Κάλυψη ορθογωνίων πολυγώνων τύπου 3 με το ελάχιστο πλήθος r-αστέρων».

ΠΕΡΙΛΗΨΗ

Ενδιαφερόμαστε για το πρόβλημα της κάλυψης απλών ορθογωνίων πολυγώνων (δηλαδή, πολυγώνων οι ακμές των οποίων είναι είτε οριζόντιες είτε κατακόρυφες) με το ελάχιστο πλήθος r-αστέρων. Ένα ορθογώνιο πολύγωνο Ρ είναι ένας r-αστέρας εάν υπάρχει σημείο p στο P τέτοιο ώστε για κάθε σημείο q του P το ευθύγραμμο τμήμα pq να ανήκει εξ ολοκλήρου στο P. Το πρόβλημα μελετήθηκε από τους Worman και Keil που περιέγραψαν έναν αλγόριθμο πολυπλοκότητας χρόνου O(n17 poly-log n) όπου n το πλήθος κορυφών του δοθέντος πολυγώνου.
Σε αυτή τη διάλεξη, θα επικεντρώσουμε το ενδιαφέρον μας στο προαναφερθέν πρόβλημα για ορθογώνια πολύγωνα τύπου 3, δηλαδή, ορθογώνια πολύγωνα που έχουν εσοχές κατά μήκος το πολύ τριών από τις τέσσερις φορές των αξόνων. Αποδεικνύουμε γεωμετρικές ιδιότητες αυτής της κατηγορίας ορθογωνίων πολυγώνων χάρις στις οποίες περιγράφουμε έναν αλγόριθμο O(n + k log k) χρόνου όπου k είναι το ελάχιστο πλήθος r-αστέρων που απαιτούνται για την κάλυψη του ορθογωνίου πολυγώνου τύπου 3 που έχει δοθεί ως είσοδος. Χρήσιμες ιδέες από τον αλγόριθμό μας ενδέχεται να μπορούν να γενικευθούν ώστε να αποδώσουν ταχύτερους αλγορίθμους για το πρόβλημα σε γενικά ορθογώνια πολύγωνα. Για τέτοια πολύγωνα, ο αλγόριθμός μας συνεπάγεται έναν 2-προσεγγιστικό αλγόριθμο.

Πρόκειται για ερευνητική εργασία που έχει προκύψει από συνεργασία με τον Πέτρο Τζίμα.
©2010 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING - UNIVERSITY OF IOANNINA
created by data|SCIENCE

Valid XHTML 1.0 Strict Valid CSS!