Προσεγγιστικοί Αλγόριθμοι Για Την Κάλυψη Πολυγωνικών Περιοχών

Abstract

Η ανάπτυξη των ασύρματων δικτύων επικοινωνίας (κινητά τηλέφωνα, κλπ) έχει δημιουργήσει πολλά προβλήματα έρευνας: ελαχιστοποίηση του αριθμού των σταθμών, ελαχιστοποίηση των χρησιμοποιούμενων συχνοτήτων, κλπ. Δύο σημεία μπορούν να επικοινωνήσουν αν καλύπτονται (δηλαδή επικοινωνούν) με ένα σταθμό. Είναι γνωστό το πρόβλημα της τοποθέτησης ενός ελάχιστου αριθμού σταθμών έτσι ώστε όλα τα σημεία να καλύπτονται. Μια παραλλαγή αυτού του προβλήματος είναι: πώς μπορούμε να τοποθετήσουμε ένα δεδομένο αριθμό σταθμών έτσι ώστε να καλύπτεται ένας μέγιστος αριθμός σημείων; Η τοπολογία της περιοχής καθορίζει εάν η επικοινωνία μεταξύ δύο σημείων είναι δυνατή ή όχι. Το μοντέλο θα πρέπει να κρατά τα χαρακτηριστικά της περιοχής. Γραφήματα, τεραίν, πολύγωνα με ή χωρίς τρύπες, κλπ, έχουν χρησιμοποιηθεί σαν μοντέλα.Εδώ μελετούμε μια σειρά από προβλήματα κάλυψης πολυγώνων με ή χωρίς τρύπες. Ειδικότερα, εξετάζονται περιπτώσεις στις οποίες ο στόχος είναι η κάλυψη μιας μέγιστης αξίας από δεδομένες περιοχές με αξία που βρίσκονται πάνω στην περίμετρο ή στο εσωτερικό του πολυγώνου χρησιμοποιώντας έναν αριθμό από φύλακες με δεδομένο ανώτατο συνολικό κόστος. Οι φύλακες (σταθμοί) τοποθετούνται πάνω στην περίμετρο του πολυγώνου.Αποδεικνύουμε ότι όλες αυτές οι περιπτώσεις είναι NP-hard. Ειδικότερα, προτείνουμε προσεγγιστικούς αλγόριθμους πολυωνυμικού χρόνου με σταθερούς παράγοντες προσέγγισης. Αποδεικνύουμε επίσης ότι όλες αυτές οι περιπτώσεις είναι APX-hard και συνεπώς APX-complete: κατασκευάζουμε μια αναγωγή διατήρησης χάσματος. Δείχνουμε ότι με λίγες μετατροπές μπορούμε να εφαρμόσουμε αυτήν την αναγωγή σε μια σειρά προβλημάτων υπολογιστικής γεωμετρίας.Γίνεται επίσης μελέτη κάποιων προβλημάτων σε γράφους αποδεικνύοντας ότι αυτά τα προβλήματα είναι ευκολότερα σε γράφους ορατότητας από ότι σε γενικούς γράφους (πχ. Maximum Clique Cover).Κατά τη διάρκεια της μελέτης των παραπάνω προβλημάτων, εισάγαμε τα εξής νέα στοιχεία: α) βάρη ή αξίες σε τμήματα της περιμέτρου του πολυγώνου και σε περιοχές στο εσωτερικό του πολυγώνου, β) κόστος σε κάθε υποψήφια θέση φύλακα (σταθμού), γ) την χρήσιμη έννοια της επίβλεψης (watching) ενός συνόλου σημείων, τμημάτων, ή περιοχών του πολυγώνου και δ) έναν τρόπο κατακερματισμού της περιμέτρου και του εσωτερικού του πολυγώνου ως προς την ορατότητα.Τέλος, ορίζουμε μια ενδιαφέρουσα παραλλαγή του προβλήματος SET COVER όπου τα στοιχεία των συνόλων έχουν διαστάσεις.