Προσεγγιστική καταμέτρηση περιοχής

Abstract

Η παρούσα εργασία πραγματεύεται την προσεγγιστική καταμέτρηση και αναζήτηση περιοχής (approximate range counting - searching) η οποία συγκαταλέγεται στα κυριότερα προβλήματα της υπολογιστικής γεωμετρίας. Στο 1ο κεφάλαιο γίνεται μια εισαγωγή στις έννοιες της υπολογιστικής γεωμετρίας για την καλύτερη κατανόηση του επιστημονικού χώρου. Δίδονται παραδείγματα εφαρμογής της στο σύγχρονο κόσμο και εξηγούνται οι βασικές έννοιες των δομών για ερωτήσεις περιοχής (range searching). Στο 2ο κεφάλαιο παρουσιάζεται το πρόβλημα αναζήτησης περιοχής. Για την καλύτερη κατανόηση του προβλήματος παρουσιάζουμε συγκεκριμένες δεντρικές δομές δεδομένων, Range Trees και k-d Trees. Στο 3ο κεφάλαιο αναλύεται το Balanced Box-Decomposition δέντρο (BBD-Tree) και η σημασία του για την επίλυση του παραπάνω προβλήματος. Επιπλέον, αναλύεται η δυναμική δομή δεδομένων «quadtreap», η οποία χρησιμοποιείται για την αποθήκευση πολυδιάστατων συνόλων από σημεία. Παρατίθεται, τέλος, και ο αλγόριθμος για την απάντηση ερωτημάτων προσεγγιστικής καταμέτρησης περιοχής χρησιμοποιώντας τη δομή quadtreap. Στο 4o κεφάλαιο ερευνούμε τα ε-ΝΝ ερωτήματα πλησιέστερου γείτονα (nearest neighbor queries) στο πεδίο των παράλληλων τμημάτων. Παρουσιάζουμε μια δομή δεδομένων που απαντά σε χρονικά-εξαρτώμενα ε-NN ερωτήματα σε οποιαδήποτε σταθερή διάσταση. Επιπλέον, παρουσιάζουμε μια μέθοδο που μειώνει τόσο τον χώρο όσο και τον χρόνο στα ερωτήματα πλησιέστερου γείτονα. Τέλος, ερευνούμε τα ερωτήματα αναζήτησης ε-ΝΝ με περιορισμένο βάρος και παρουσιάζουμε ένα βασικό θεώρημα.