The prevalence of computer graphics technology boosts the development of point clouds, which offer advantages over T riangular I rregular N etworks , i.e., TIN s, in proximity queries. All existing on-the-fly shortest path query algorithms and oracles on a TIN are expensive, and no algorithms can answer shortest path queries on a point cloud directly. Thus, we propose two types of efficient shortest path oracles on a point cloud. They answer the shortest path query between (1) a pair of P oints- O f- I nterests ( POIs ), and (2) any point and a POI, respectively. We propose four adaptations of them to answer the query between any point and a POI (or any point if no POIs are given). We also propose two efficient proximity query algorithms using these oracles. Our two oracles and their proximity query algorithms outperform the best-known adapted oracle by 12 to 42,000 times in terms of the oracle construction time, oracle size and proximity query time, respectively 1 .

The booming of computer graphics technology facilitates the growing use of terrain data. Notably, shortest path querying on a terrain surface is central in a range of applications and has received substantial attention from the database community. Despite this, computing the shortest paths on-the-fly on a terrain surface remains very expensive, and all existing oracle-based algorithms are only efficient when the terrain surface is fixed. They rely on large data structures that must be re-constructed from scratch when updates to the terrain surface occur, which is very time-consuming. To advance the state-of-the-art, we propose an efficiently updatable$(1+\epsilon )$-approximate shortest path oracle for a set ofPoints-Of-Interests(POIs) on an updated terrain surface, and it can be easily adapted to the case if POIs are not given as input. Our experiments show that when POIs are given (resp. not given), our oracle is up to 88 times, 12 times, and 3 times (resp. 15 times, 50 times, and 100 times) better than the best-known oracle on terrain surfaces in terms of the oracle update time, output size, and shortest path query.

Studying the shortest path query for moving objects on a terrain surface has aroused widespread concern in industry and academia. In this paper, we study the weighted region problem, which aims at finding the shortest path between two points passing different regions on a 3D weighted terrain surface and different regions are assigned different weights. We propose an efficient (1 + ϵ)-approximate on-the-fly algorithm to solve it. Our experimental results show that our algorithm is up to 1630 times and 40 times better than the best-known algorithm in terms of running time and memory usage in realistic settings1.

The prevalence of computer graphics technology boosts the developments of point clouds in recent years, which offer advantages over terrain surfaces (represented by Triangular Irregular Networks, i.e., TINs) in proximity queries, including the shortest path query, the k-Nearest Neighbor (kNN) query and the range query. Since (1) all existing on-the-fly and oracle-based shortest path query algorithms on a TIN are very expensive, (2) all existing on-the-fly shortest path query algorithms on a point cloud are still not efficient, and (3) there are no oracle-based shortest path query algorithms on a point cloud, we propose an efficient (1+ε)-approximate shortest path oracle that answers the shortest path query for a set of Points-Of-Interests (POIs) on the point cloud, which has a good performance (in terms of the oracle construction time, oracle size and shortest path query time) due to the concise information about the pairwise shortest paths between any pair of POIs stored in the oracle. Our oracle can be easily adapted to answering the shortest path query for any points on the point cloud if POIs are not given as input, and also achieve a good performance. Then, we propose efficient algorithms for answering the (1+ε)-approximate kNN and range query with the assistance of our oracle. Our experimental results show that when POIs are given (resp. not given) as input, our oracle is up to 390 times, 30 times and 6 times (resp. 500 times, 140 times and 50 times) better than the best-known oracle on a TIN in terms of the oracle construction time, oracle size and shortest path query time, respectively. Our algorithms for the other two proximity queries are both up to 100 times faster than the best-known algorithms.

The shortest path in both the two dimensional (2D) plane and the three dimensional (3D) terrain is extensively used both in industry and academia. Although there are some map visualization tools for viewing the shortest path in 2D and 3D views, we find two limitations: (1) they are not applicable for map applications with obstacles (such as the wall in a building), and (2) they look unrealistic and strange when a road network approach is blindly adopted. Motivated by this, we developed a web-based multi-functional campus map tool called Path Advisor , which allows users to visualize the shortest path in the 2D view, the bird's eye view and the virtual reality view (VR view). Path Advisor uses Dijkstra's shortest path algorithm and breadth-first tree in the 2D view, and the weighted shortest surface path algorithm in the bird's eye view and the VR view. We shot a video for demonstrating Path Advisor at https://youtu.be/ZgdjyXXHwqg.