Efficient Computation of the Optimal Accessible Location for a Group of Mobile Agents

• Published in: ACM transactions on spatial algorithms and systems 2018-12, Vol.4 (4), p.1-32
• Main Authors: Khan, A. K. M. Mustafizur Rahman, Kulik, Lars, Tanin, Egemen, Hua, Hua, Hashem, Tanzima
• Format: Article
• Language: English
• ISSN: 2374-0353; 2374-0361
• DOI: 10.1145/3239124

Nowadays, people can access location-based services (LBSs) as a group via mobile devices to plan their daily activities with friends and relatives. In this article, we introduce an important class of group-oriented LBSs, group optimal accessible location (GOAL) queries that enable users to identify the location of a point of interest (POI) that has the minimum total distance to a given set of paths. GOAL queries have many applications, such as the selection of an optimal location for group meet-ups or for a mobile facility such as a food truck. In a GOAL query, each trip or path is represented as a set of line segments, and the distance of a POI from a path is computed as the minimum distance of the POI to any line segment of the path. We develop an efficient approach to evaluate GOAL queries. The novelty of our GOAL query processing algorithm in contrast to other spatial query processing algorithms is the reformulation of a GOAL query by considering only a subset of path segments from the given set of paths, which is also the key factor behind the efficiency of our proposed algorithm. We exploit geometric properties and develop pruning techniques to eliminate both POIs and path segments that cannot provide the optimal solution for a GOAL query. Our experimental results demonstrate that we provide a readily deployable solution for real-life applications.