Skip navigation

Identifying surrounds and engulfs relations in mobile and coordinate-free geosensor networks

Identifying surrounds and engulfs relations in mobile and coordinate-free geosensor networks

Both, Alan, Duckham, Matt and Worboys, Michael (2018) Identifying surrounds and engulfs relations in mobile and coordinate-free geosensor networks. ACM Transactions on Spatial Algorithms and Systems, 4 (2):6. ISSN 2374-0353 (Print), 2374-0361 (Online) (doi:https://doi.org/10.1145/3234505)

[img]
Preview
PDF (Author Accepted Manuscript)
19723 WORBOYS_Identifying_Surrounds_and_Engulfs_Relations_2018.pdf - Accepted Version

Download (492kB) | Preview

Abstract

This paper concerns the definition and identification of qualitative spatial relationships for the full and partial enclosure of spatial regions. The paper precisely defines three relationships between regions, 'surrounds', 'engulfs', and 'envelops', highlighting the correspondence to similar definitions in the literature. An efficient algorithm capable of identifying these qualitative spatial relations in a network of dynamic (mobile) geosensor nodes is developed and tested. The algorithms are wholly decentralized, and operate in-network with no centralized control. The algorithms are also ``coordinate-free,'' able to operate in distributed spatial computing environments where coordinate locations are expensive to capture or otherwise unavailable. Experimental evaluation of the algorithms designed demonstrates the efficiency of the approach. Although the algorithm communication complexity is dominated by an overall worst-case O(n^2) leader election algorithm, the experiments show in practice an average-case complexity approaching linear, O(n^{1.1}).

Item Type: Article
Uncontrolled Keywords: geosensor network qualitative spatial reasoning map tree
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Computing & Information Systems
Last Modified: 17 May 2019 10:29
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: GREAT a
Selected for GREAT 2019: GREAT 2
URI: http://gala.gre.ac.uk/id/eprint/19723

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics