{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T16:40:10Z","timestamp":1758904810198,"version":"3.44.0"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"4","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":[[2025,9,22]]},"abstract":"<jats:p>\n            Performing proximity queries on a 3D surface has gained significant attention from both academic and industry. The height map is one fundamental 3D surface representation with many advantages over others such as the point cloud and\n            <jats:italic toggle=\"yes\">Triangular-Irregular Network<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">TIN<\/jats:italic>\n            ). In this paper, we study the shortest path query on a height map. Since performing proximity queries using the shortest path on a height map is costly, we propose a simplification algorithm on the height map to accelerate it. We also propose a shortest path query algorithm and algorithms for answering proximity queries on the original\/simplified height map. Our experiments show that our simplification algorithm is up to 21 times and 5 times (resp. 412 times and 7 times) better than the best-known adapted point cloud (resp.\n            <jats:italic toggle=\"yes\">TIN<\/jats:italic>\n            ) simplification algorithm in terms of the simplification time and output size (the size of the simplified surface), respectively. Performing proximity queries on our simplified height map is up to 5 times and 1,340 times quicker than on the simplified point cloud and the simplified\n            <jats:italic toggle=\"yes\">TIN<\/jats:italic>\n            with an error at most 10%, respectively.\n          <\/jats:p>","DOI":"10.1145\/3749162","type":"journal-article","created":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T17:17:03Z","timestamp":1758647823000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Proximity Queries on Simplified Height Maps"],"prefix":"10.1145","volume":"3","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":[[2025,9,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. 1.5 Billion the world's most expensive imaging satellite nisar. https:\/\/syntheticapertureradar.com\/nasa-isro-sarproject-nisar\/"},{"key":"e_1_2_1_2_1","unstructured":"2025. 125 Years of topographic mapping. https:\/\/www.esri.com\/news\/arcnews\/fall09articles\/125-years.html"},{"key":"e_1_2_1_3_1","unstructured":"2025. 50 Years of Landsat Science. https:\/\/landsat.gsfc.nasa.gov"},{"key":"e_1_2_1_4_1","unstructured":"2025. Avalanche. https:\/\/en.wikipedia.org\/wiki\/Avalanche"},{"key":"e_1_2_1_5_1","unstructured":"2025. Climate and average weather year round in Gates of the Arctic National Park. https:\/\/weatherspark.com\/y\/150336\/Average-Weather-in-Gates-of-the-Arctic-National-Park-Alaska-United-States-Year-Round"},{"key":"e_1_2_1_6_1","unstructured":"2025. Data geocomm. http:\/\/data.geocomm.com\/"},{"key":"e_1_2_1_7_1","unstructured":"2025. The earth. https:\/\/www.nationsonline.org\/oneworld\/earth.htm"},{"volume-title":"Geocento commercial sar satellite imagery resolutions","year":"2022","key":"e_1_2_1_8_1","unstructured":"2025. Geocento commercial sar satellite imagery resolutions 2022, by cost per scene. https:\/\/www.statista.com\/statistics\/1293899\/geocento-commercial-satellite-sar-imagery-resolution-cost-worldwide\/"},{"key":"e_1_2_1_9_1","unstructured":"2025. Google Earth. https:\/\/earth.google.com\/web"},{"key":"e_1_2_1_10_1","unstructured":"2025. Google Map. https:\/\/www.google.com\/maps"},{"key":"e_1_2_1_11_1","unstructured":"2025. Google Maps Platform. https:\/\/mapsplatform.google.com"},{"key":"e_1_2_1_12_1","unstructured":"2025. Gunnison national forest. https:\/\/gunnisoncrestedbutte.com\/visit\/places-to-go\/parks-and-outdoors\/gunnisonnational-forest\/"},{"key":"e_1_2_1_13_1","unstructured":"2025. The history of point cloud development. https:\/\/www.linkedin.com\/pulse\/history-point-cloud-developmentbimprove\/"},{"key":"e_1_2_1_14_1","unstructured":"2025. How satellites work. https:\/\/science.howstuffworks.com\/satellite10.htm"},{"key":"e_1_2_1_15_1","unstructured":"2025. Laramie mountain. https:\/\/www.britannica.com\/place\/Laramie-Mountains"},{"key":"e_1_2_1_16_1","unstructured":"2025. Metaverse. https:\/\/about.facebook.com\/meta"},{"key":"e_1_2_1_17_1","unstructured":"2025. Open digital elevation model. https:\/\/www.opendem.info\/"},{"key":"e_1_2_1_18_1","unstructured":"2025. Preferred walking speed. https:\/\/en.wikipedia.org\/wiki\/Preferred_walking_speed"},{"key":"e_1_2_1_19_1","unstructured":"2025. Robinson mountain. https:\/\/www.mountaineers.org\/activities\/routes-places\/robinson-mountain"},{"key":"e_1_2_1_20_1","unstructured":"2025. Shuttle radar topography mission. https:\/\/www.earthdata.nasa.gov\/data\/instruments\/srtm"},{"key":"e_1_2_1_21_1","unstructured":"2025. Transparent pricing for commercial Earth observation imagery. https:\/\/skyfi.com\/en\/pricing"},{"key":"e_1_2_1_22_1","unstructured":"2025. Zoom earth. https:\/\/zoom.earth\/maps\/"},{"key":"e_1_2_1_23_1","volume-title":"Evaluating the performance of various interpolation techniques on digital elevation models in highly dense forest vegetation environment. Ecological Informatics (EI) 81","author":"Adedapo Segun M","year":"2024","unstructured":"Segun M Adedapo and Hamdi A Zurqani. 2024. Evaluating the performance of various interpolation techniques on digital elevation models in highly dense forest vegetation environment. Ecological Informatics (EI) 81 (2024)."},{"key":"e_1_2_1_24_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). 139--147","author":"Agarwal Pankaj K","year":"1997","unstructured":"Pankaj K Agarwal and Pavan K Desikan. 1997. An efficient algorithm for terrain simplification. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 139--147."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECMR50962.2021.9568799"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2022.104287"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90073-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_1_29_1","unstructured":"The Conversation. 2025. 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-upwinter-storms-175628"},{"volume-title":"Introduction to algorithms","author":"Cormen Thomas H","key":"e_1_2_1_30_1","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.152"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0053-2"},{"key":"e_1_2_1_33_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_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aei.2024.102648"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3678717.3691218"},{"key":"e_1_2_1_36_1","unstructured":"Fresh Off The Grid. 2025. 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_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467337"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA57147.2024.10610105"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1080\/10095020.2023.2270520"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237216"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtrangeo.2021.103271"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588694"},{"key":"e_1_2_1_43_1","first-page":"343","article-title":"Accuracy of handheld gps compairing with total station in land use survey: a case study in RUET campus","volume":"7","author":"Kamruzzaman Md","year":"2014","unstructured":"Md Kamruzzaman, Tanzila Islam, and Smrity Rani Poddar. 2014. Accuracy of handheld gps compairing with total station in land use survey: a case study in RUET campus. International Journal of Innovation and Applied Studies (IJIAS) 7, 1 (2014), 343.","journal-title":"International Journal of Innovation and Applied Studies (IJIAS)"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850591"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732226"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0027-5"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRD.2023.3265415"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i4.28102"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989369"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018432.1021532"},{"key":"e_1_2_1_52_1","volume-title":"International Symposium on Algorithms and Computation (ISAAC). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 52--1.","author":"Oh Eunjin","year":"2020","unstructured":"Eunjin Oh. 2020. Shortest-path queries in geometric networks. In International Symposium on Algorithms and Computation (ISAAC). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 52--1."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isprsjprs.2024.03.023"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.53"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687763"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1051\/e3sconf\/202449702024"},{"key":"e_1_2_1_57_1","unstructured":"National Park Service. 2025. Gates of the Arctic. https:\/\/www.nps.gov\/gaar\/index.htm"},{"key":"e_1_2_1_58_1","unstructured":"National Weather Service. 2025. Measuring Snow. https:\/\/www.weather.gov\/dvn\/snowmeasure"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453966"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.3390\/agronomy12040836"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.56"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14358\/PERS.87.3.207"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10015-020-00617-3"},{"volume-title":"ACM International Conference on Management of Data (SIGMOD)","author":"Wei Victor Junqiu","key":"e_1_2_1_64_1","unstructured":"Victor Junqiu Wei, Raymond Chi-Wing Wong, Cheng Long, and David M. Mount. 2017. Distance oracle on terrain surface. In ACM International Conference on Management of Data (SIGMOD). New York, NY, USA, 1211--1226."},{"key":"e_1_2_1_65_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_1_66_1","first-page":"1","article-title":"On efficient shortest path computation on terrain surface: a direction-oriented approach","volume":"1","author":"Wei Victor Junqiu","year":"2024","unstructured":"Victor Junqiu Wei, Raymond Chi-Wing Wong, Cheng Long, David M Mount, and Hanan Samet. 2024. On efficient shortest path computation on terrain surface: a direction-oriented approach. IEEE Transactions on Knowledge & Data Engineering (TKDE) 1 (2024), 1--14.","journal-title":"IEEE Transactions on Knowledge & Data Engineering (TKDE)"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687753"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396880"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476319"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM61037.2024.00023"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639261"},{"key":"e_1_2_1_73_1","unstructured":"Yinzhao Yan and Raymond Chi-Wing Wong. 2025. Efficient proximity queries on simplified height map (technical report). https:\/\/github.com\/yanyinzhao\/HeightMapPathCode\/blob\/main\/TechnicalReport.pdf"},{"key":"e_1_2_1_74_1","first-page":"1","article-title":"An efficiently updatable path oracle for terrain surfaces","volume":"1","author":"Yan Yinzhao","year":"2024","unstructured":"Yinzhao Yan, Raymond Chi-Wing Wong, and Christian S Jensen. 2024. An efficiently updatable path oracle for terrain surfaces. IEEE Transactions on Knowledge & Data Engineering (TKDE) 1 (2024), 1--14.","journal-title":"IEEE Transactions on Knowledge & Data Engineering (TKDE)"},{"key":"e_1_2_1_75_1","volume-title":"Geodesics on point clouds. Mathematical Problems in Engineering (MPE) 2014","author":"Yu Hongchuan","year":"2014","unstructured":"Hongchuan Yu, Jian J Zhang, and Zheng Jiao. 2014. Geodesics on point clouds. Mathematical Problems in Engineering (MPE) 2014 (2014)."},{"key":"e_1_2_1_76_1","volume-title":"A Predictive Model Based on TripAdvisor Textual Reviews: Early Destination Recommendations for Travel Planning. SAGE Open 14, 2","author":"Zhang Yating","year":"2024","unstructured":"Yating Zhang, Hongbo Tan, Qi Jiao, Zhihao Lin, Zesen Fan, Dengming Xu, Zheng Xiang, Rob Law, and Tianxiang Zheng. 2024. A Predictive Model Based on TripAdvisor Textual Reviews: Early Destination Recommendations for Travel Planning. SAGE Open 14, 2 (2024)."},{"key":"e_1_2_1_77_1","volume-title":"A robot navigation system in complex terrain based on statistical features of point clouds","author":"Zhang Yifei","year":"2023","unstructured":"Yifei Zhang and Shiyuan Wang. 2023. A robot navigation system in complex terrain based on statistical features of point clouds. IEEE Transactions on Intelligent Vehicles (TIV) (2023)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T16:22:11Z","timestamp":1758903731000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,22]]},"references-count":77,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,9,22]]}},"alternative-id":["10.1145\/3749162"],"URL":"https:\/\/doi.org\/10.1145\/3749162","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,9,22]]}}}