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:10.1145/3234505)

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 / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Last Modified:	04 Mar 2022 13:06
URI:	http://gala.gre.ac.uk/id/eprint/19723

Actions (login required)

View Item

Downloads