{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T08:42:18Z","timestamp":1769935338465,"version":"3.49.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Guangzhou Fund","award":["GZSTI16EG24"],"award-info":[{"award-number":["GZSTI16EG24"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>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+\u03b5)-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+\u03b5)-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.<\/jats:p>","DOI":"10.1145\/3639261","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":5,"title":["Proximity Queries on Point Clouds using Rapid Construction Path Oracle"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6261-1569","authenticated-orcid":false,"given":"Yinzhao","family":"Yan","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7045-6503","authenticated-orcid":false,"given":"Raymond Chi-Wing","family":"Wong","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2022. Blender. https:\/\/www.blender.org"},{"key":"e_1_2_2_2_1","unstructured":"2022. Google Earth. https:\/\/earth.google.com\/web"},{"key":"e_1_2_2_3_1","unstructured":"2022. Robinson Mountain. https:\/\/www.mountaineers.org\/activities\/routes-places\/robinson-mountain"},{"key":"e_1_2_2_4_1","unstructured":"2023. Cyberpunk 2077. https:\/\/www.cyberpunk.net"},{"key":"e_1_2_2_5_1","unstructured":"2023. Data Geocomm. http:\/\/data.geocomm.com\/"},{"key":"e_1_2_2_6_1","unstructured":"2023. Google Map. https:\/\/www.google.com\/maps"},{"key":"e_1_2_2_7_1","unstructured":"2023. Gunnison National Forest. https:\/\/gunnisoncrestedbutte.com\/visit\/places-to-go\/parks-and-outdoors\/gunnison-national-forest\/"},{"key":"e_1_2_2_8_1","unstructured":"2023. Laramie Mountain. https:\/\/www.britannica.com\/place\/Laramie-Mountains"},{"key":"e_1_2_2_9_1","unstructured":"2023. Preferred walking speed. https:\/\/en.wikipedia.org\/wiki\/Preferred_walking_speed"},{"key":"e_1_2_2_10_1","unstructured":"Mithil Aggarwal. 2022. More than 60 killed in blizzard wreaking havoc across U.S. https:\/\/www.cnbc.com\/2022\/12\/26\/death-toll-rises-to-at-least-55-as-freezing-temperatures-and-heavy-snow-wallop-swaths-of-us.html"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1088\/1755-1315\/221\/1\/012082"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113816"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/AERO.2007.352683"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154"},{"key":"e_1_2_2_16_1","unstructured":"The Conversation. 2022. How is snowfall measured? A meteorologist explains how volunteers tally up winter storms. https:\/\/theconversation.com\/how-is-snowfall-measured-a-meteorologist-explains-how-volunteers-tally-up-winter-storms-175628"},{"key":"e_1_2_2_17_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2020.3023541"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.152"},{"key":"e_1_2_2_20_1","volume-title":"International Workshop on Web and Wireless Geographical Information Systems. Springer, 151--166","author":"Deng Ke","year":"2004","unstructured":"Ke Deng and Xiaofang Zhou. 2004. Expansion-based algorithms for finding single pair shortest path on surface. In International Workshop on Web and Wireless Geographical Information Systems. Springer, 151--166."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0053-2"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-7998.2006.00215.x"},{"key":"e_1_2_2_23_1","volume-title":"A note on two problems in connexion with graphs. Numerische mathematik 1, 1","author":"Dijkstra Edsger W","year":"1959","unstructured":"Edsger W Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1, 1 (1959), 269--271."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5220\/0005002000200028"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2016.02.002"},{"key":"e_1_2_2_26_1","unstructured":"Fresh Off The Grid. 2022. Winter Hiking 101: Everything you need to know about hiking in snow. https:\/\/www.freshoffthegrid.com\/winter-hiking-101-hiking-in-snow\/"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588694"},{"key":"e_1_2_2_29_1","unstructured":"GreenValley International. 2023. 3D Point Cloud Data and the Production of Digital Terrain Models. https:\/\/geo-matching.com\/content\/3d-point-cloud-data-and-the-production-of-digital-terrain-models"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850591"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732226"},{"key":"e_1_2_2_32_1","volume-title":"The 7th central European seminar on computer graphics","author":"K\u00f6rtgen Marcel","unstructured":"Marcel K\u00f6rtgen, Gil-Joo Park, Marcin Novotni, and Reinhard Klein. 2003. 3D shape matching with 3D shape contexts. In The 7th central European seminar on computer graphics, Vol. 3. Citeseer, 5--17."},{"key":"e_1_2_2_33_1","volume-title":"Communications and Information Technology proceedings","author":"Koyuncu Baki","year":"2009","unstructured":"Baki Koyuncu and Erkan Bostanci. 2009. 3D battlefield modeling and simulation of war games. Communications and Information Technology proceedings (2009)."},{"key":"e_1_2_2_34_1","unstructured":"Russell LaDuca. 2020. What would happen to me if I was buried under snow? https:\/\/qr.ae\/prt6zQ"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0027-5"},{"key":"e_1_2_2_36_1","volume-title":"All one needs to know about metaverse: A complete survey on technological singularity, virtual ecosystem, and research agenda. arXiv preprint arXiv:2110.05352","author":"Lee Lik-Hang","year":"2021","unstructured":"Lik-Hang Lee, Tristan Braud, Pengyuan Zhou, Lin Wang, Dianlei Xu, Zijun Lin, Abhishek Kumar, Carlos Bermejo, and Pan Hui. 2021. All one needs to know about metaverse: A complete survey on technological singularity, virtual ecosystem, and research agenda. arXiv preprint arXiv:2110.05352 (2021)."},{"key":"e_1_2_2_37_1","volume-title":"When creators meet the metaverse: A survey on computational arts. arXiv preprint arXiv:2111.13486","author":"Lee Lik-Hang","year":"2021","unstructured":"Lik-Hang Lee, Zijun Lin, Rui Hu, Zhengya Gong, Abhishek Kumar, Tangyao Li, Sijia Li, and Pan Hui. 2021. When creators meet the metaverse: A survey on computational arts. arXiv preprint arXiv:2111.13486 (2021)."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.3015992"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989369"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1139\/z02-061"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_42_1","unstructured":"Geo Week News. 2022. Tesla using radar to generate point clouds for autonomous driving. https:\/\/www.geoweeknews.com\/news\/tesla-using-radar-generate-point-clouds-autonomous-driving"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings. International Database Engineering and Applications Symposium, 2004. IDEAS'04. IEEE, 334--343","author":"Ng Hoong Kee","year":"2004","unstructured":"Hoong Kee Ng, Hon Wai Leong, and Ngai Lam Ho. 2004. Efficient algorithm for path-based range query in spatial databases. In Proceedings. International Database Engineering and Applications Symposium, 2004. IDEAS'04. IEEE, 334--343."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geomorph.2005.10.001"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2016.07.734"},{"key":"e_1_2_2_46_1","volume-title":"International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 34","author":"Remondino Fabio","year":"2003","unstructured":"Fabio Remondino. 2003. From point cloud to surface: the modeling and visualization problem. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences 34 (2003)."},{"key":"e_1_2_2_47_1","unstructured":"National Park Service. 2022. Mount Rainier. https:\/\/www.nps.gov\/mora\/index.htm"},{"key":"e_1_2_2_48_1","unstructured":"National Park Service. 2022. Mount Rainier Annual Snowfall Totals. https:\/\/www.nps.gov\/mora\/planyourvisit\/annual-snowfall-totals.htm"},{"key":"e_1_2_2_49_1","unstructured":"National Park Service. 2022. Mount Rainier Frequently Asked Questionss. https:\/\/www.nps.gov\/mora\/faqs.htm"},{"key":"e_1_2_2_50_1","unstructured":"National Weather Service. 2023. Measuring Snow. https:\/\/www.weather.gov\/dvn\/snowmeasure"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453966"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/11744023_1"},{"key":"e_1_2_2_53_1","volume-title":"Approximating the riemannian metric from point clouds via manifold moving least squares. arXiv preprint arXiv:2007.09885","author":"Sober Barak","year":"2020","unstructured":"Barak Sober, Robert Ravier, and Ingrid Daubechies. 2020. Approximating the riemannian metric from point clouds via manifold moving least squares. arXiv preprint arXiv:2007.09885 (2020)."},{"key":"e_1_2_2_54_1","unstructured":"Spatial. 2022. LiDAR Scanning with Spatial's iOS App. https:\/\/support.spatial.io\/hc\/en-us\/articles\/360057387631-LiDAR-Scanning-with-Spatial-s-iOS-App"},{"key":"e_1_2_2_55_1","volume-title":"Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data. 1211--1226","author":"Wei Victor Junqiu","unstructured":"Victor Junqiu Wei, Raymond Chi-Wing Wong, Cheng Long, and David M. Mount. 2017. Distance oracle on terrain surface. In Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data. 1211--1226."},{"key":"e_1_2_2_56_1","volume-title":"Cheng Long, David M Mount, and Hanan Samet.","author":"Wei Victor Junqiu","year":"2022","unstructured":"Victor Junqiu Wei, Raymond Chi-Wing Wong, Cheng Long, David M Mount, and Hanan Samet. 2022. Proximity queries on terrain surface. ACM Transactions on Database Systems (TODS) (2022)."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687753"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396880"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476319"},{"key":"e_1_2_2_61_1","unstructured":"Yinzhao Yan and Raymond Chi-Wing Wong. 2023. Proximity queries on point cloud using rapid construction path oracle (technical report). https:\/\/github.com\/yanyinzhao\/PointCloudPathCode\/blob\/master\/TechnicalReport.pdf"},{"key":"e_1_2_2_62_1","volume-title":"Geodesics on point clouds. Mathematical Problems in Engineering 2014","author":"Yu Hongchuan","year":"2014","unstructured":"Hongchuan Yu, Jian J Zhang, and Zheng Jiao. 2014. Geodesics on point clouds. Mathematical Problems in Engineering 2014 (2014)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639261","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:11:36Z","timestamp":1755789096000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639261"],"URL":"https:\/\/doi.org\/10.1145\/3639261","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}