Efficient algorithms for computing optimal meeting points in the obstructed space

Abstract

In this thesis, we introduce an Obstructed Optimal M eeting P oint (OOMP) query that enables a group of users to identify a meeting location with the minimum total travel distance in presence of obstacles. For example, a group of friends located at di erent locations in the park or in a city center may want to meet at a point that minimizes the total distance of the group members. However, in the park or city center they may have to face many obstacles like trees or lakes and buildings in their walking paths. In recent years, the problem of nding optimal meeting point (OMP) has been addressed in the Euclidean space and road networks which ignores the presence of obstacles. We show that the problem of nding OMP in the obstructed space is NP-hard. We introduce heuristic algorithm for processing an OOMP query. Processing an OOMP query in the obstructed space is an exhaustive search, as the search space is in nite and lled with obstacles. To identify the optimal meeting point, computing the total obstructed distance for every point in the search space would incur extremely high processing overhead as nding the obstructed distance between two locations is an expensive computation. Thus, the major challenges for an OOMP query is to re ne the search space and compute the total obstructed distance with reduced processing overhead. We exploit geometric properties and hierarchical structure to develop techniques to re ne the search space. In addition, we develop e cient technique to compute the total obstructed distance. Our technique reduces the number of obstacles retrieved from the database and does not retrieve the same obstacle multiple times from the database to compute multiple individual obstructed distances required for computing a total obstructed distance. The query processing overhead increases with the increase of the number of the group members, obstacles and the search space. To further decrease the processing overhead, we develop another heuristic algorithm for processing an OOMP query in real time by sacri cing accuracy. We evaluate the efficiency and effectiveness of our algorithms using real datasets and present a comparative analysis among our proposed algorithms.