Efficient Path Oracles for Proximity Queries on Point Clouds

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 .