{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T05:18:02Z","timestamp":1769059082855,"version":"3.49.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T00:00:00Z","timestamp":1630627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARC","award":["DP180102050 and DP200102611"],"award-info":[{"award-number":["DP180102050 and DP200102611"]}]},{"name":"Google Faculty Research Award","award":["NSFC 91646204"],"award-info":[{"award-number":["NSFC 91646204"]}]},{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"crossref","award":["IIS-13-20791 and IIS-1816889"],"award-info":[{"award-number":["IIS-13-20791 and IIS-1816889"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Interact. Intell. Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>Understanding urban areas of interest (AOIs) is essential in many real-life scenarios, and such AOIs can be computed based on the geographic points that satisfy user queries. In this article, we study the problem of efficient and effective visualization of user-defined urban AOIs in an interactive manner. In particular, we first define the problem of user-defined AOI visualization based on a real estate data visualization scenario, and we illustrate why a novel footprint method is needed to support the visualization. After extensively reviewing existing \u201cfootprint\u201d methods, we propose a parameter-free footprint method, named AOI-shapes, to capture the boundary information of a user-defined urban AOI. Next, to allow interactive query refinements by the user, we propose two efficient and scalable algorithms to incrementally generate urban AOIs by reusing existing visualization results. Finally, we conduct extensive experiments with both synthetic and real-world datasets to demonstrate the quality and efficiency of the proposed methods.<\/jats:p>","DOI":"10.1145\/3431817","type":"journal-article","created":{"date-parts":[[2021,9,3]],"date-time":"2021-09-03T19:30:07Z","timestamp":1630697407000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["AOI-shapes: An Efficient Footprint Algorithm\u00a0to Support Visualization of User-defined Urban Areas of Interest"],"prefix":"10.1145","volume":"11","author":[{"given":"Mingzhao","family":"Li","sequence":"first","affiliation":[{"name":"RMIT University Australia, Melbourne, Victoria, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University Australia, Melbourne, Victoria, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Farhana","family":"Choudhury","sequence":"additional","affiliation":[{"name":"University of Melbourne Australia, Parkville, Victoria, Australia, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanan","family":"Samet","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matt","family":"Duckham","sequence":"additional","affiliation":[{"name":"RMIT University Australia, Melbourne, Victoria, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timos","family":"Sellis","sequence":"additional","affiliation":[{"name":"Swinburne University of Technology Australia, Hawthorn, Victoria, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,9,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08326-1_50"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658810110038942"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90072-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2005.08.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.08.014"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"G. Berg W. Julian R. Mines and Fred Richman. 1975. The constructive Jordan curve theorem. Rocky Mount. J. Math. (1975) 225\u2013236.  G. Berg W. Julian R. Mines and Fred Richman. 1975. The constructive Jordan curve theorem. Rocky Mount. J. Math. (1975) 225\u2013236.","DOI":"10.1216\/RMJ-1975-5-2-225"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90021-2"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the ACM SIGKDD International Workshop on Urban Computing. 1\u20138.","author":"Cao Zechun","unstructured":"Zechun Cao , Sujing Wang , Germain Forestier , Anne Puissant , and Christoph F. Eick . 2013. Analyzing the composition of cities using spatial clustering . In Proceedings of the ACM SIGKDD International Workshop on Urban Computing. 1\u20138. Zechun Cao, Sujing Wang, Germain Forestier, Anne Puissant, and Christoph F. Eick. 2013. Analyzing the composition of cities using spatial clustering. In Proceedings of the ACM SIGKDD International Workshop on Urban Computing. 1\u20138."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the SIGCHI Conference. 181\u2013186","author":"Card Stuart K.","unstructured":"Stuart K. Card , George G. Robertson , and Jock D. Mackinlay . 1991. The information visualizer, an information workspace . In Proceedings of the SIGCHI Conference. 181\u2013186 . Stuart K. Card, George G. Robertson, and Jock D. Mackinlay. 1991. The information visualizer, an information workspace. In Proceedings of the SIGCHI Conference. 181\u2013186."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2016.2628398"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Russian-Korean International Symposium on Science and Technology. 112\u2013115","author":"Chadnov R. V.","unstructured":"R. V. Chadnov and A. V. Skvortsov . 2004. Convex hull algorithms review . In Proceedings of the Russian-Korean International Symposium on Science and Technology. 112\u2013115 . R. V. Chadnov and A. V. Skvortsov. 2004. Convex hull algorithms review. In Proceedings of the Russian-Korean International Symposium on Science and Technology. 112\u2013115."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712873"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.1997.0550"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.03.023"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/355759.355766"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39923-0_25"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the SIGKDD Conference. 226\u2013231","author":"Ester Martin","year":"1996","unstructured":"Martin Ester , Hans-Peter Kriegel , J\u00f6rg Sander , and Xiaowei Xu . 1996 . A density-based algorithm for discovering clusters in large spatial databases with noise . In Proceedings of the SIGKDD Conference. 226\u2013231 . Martin Ester, Hans-Peter Kriegel, J\u00f6rg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the SIGKDD Conference. 226\u2013231."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11863939_6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1111\/tgis.12289"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cvi.2009.0079"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2015.09.001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(73)90020-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom.2010.86"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cageo.2005.12.004"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/72.143377"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290612"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvlc.2018.02.001"},{"key":"e_1_2_1_29_1","volume-title":"Computer Graphics Forum","author":"Li Mingzhao","unstructured":"Mingzhao Li , Farhana Choudhury , Zhifeng Bao , Hanan Samet , and Timos Sellis . 2018. ConcaveCubes: Supporting cluster-based geographical visualization in large data scale . In Computer Graphics Forum , Vol. 37 . Wiley Online Library , 217\u2013228. Mingzhao Li, Farhana Choudhury, Zhifeng Bao, Hanan Samet, and Timos Sellis. 2018. ConcaveCubes: Supporting cluster-based geographical visualization in large data scale. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 217\u2013228."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/00045608.2014.941732"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13772-3_28"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.3138\/cart.50.2.2662"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.263005"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(99)00124-7"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2015.05.025"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the International Conference on Computer Graphics Theory and Applications. 61\u201368","author":"Moreira Adriano","year":"2007","unstructured":"Adriano Moreira and Maribel Yasmina Santos . 2007 . Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points . In Proceedings of the International Conference on Computer Graphics Theory and Applications. 61\u201368 . Adriano Moreira and Maribel Yasmina Santos. 2007. Concave hull: A k-nearest neighbours approach for the computation of the region occupied by a set of points. In Proceedings of the International Conference on Computer Graphics Theory and Applications. 61\u201368."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.224"},{"key":"e_1_2_1_38_1","first-page":"587","article-title":"A new concave hull algorithm and concaveness measure for n-dimensional datasets","volume":"28","author":"Park Jin-Seo","year":"2012","unstructured":"Jin-Seo Park and Se-Jong Oh . 2012 . A new concave hull algorithm and concaveness measure for n-dimensional datasets . J. Info. Sci. Eng. 28 (2012), 587 \u2013 600 . Jin-Seo Park and Se-Jong Oh. 2012. A new concave hull algorithm and concaveness measure for n-dimensional datasets. J. Info. Sci. Eng. 28 (2012), 587\u2013600.","journal-title":"J. Info. Sci. Eng."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2014.12.002"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5220\/0005720300570069"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W15-2810"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/359423.359430"},{"key":"e_1_2_1_43_1","volume-title":"Shamos","author":"Preparata Franco P.","year":"2012","unstructured":"Franco P. Preparata and Michael I . Shamos . 2012 . Computational Geometry : An Introduction. Springer Science & Business Media . Franco P. Preparata and Michael I. Shamos. 2012. Computational Geometry: An Introduction. Springer Science & Business Media."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056714"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45799-2_17"},{"key":"e_1_2_1_46_1","first-page":"150","article-title":"Optimal computation of finitely oriented convex hulls. Info","volume":"72","author":"Rawlins Gregory J. E.","year":"1987","unstructured":"Gregory J. E. Rawlins and Derick Wood . 1987 . Optimal computation of finitely oriented convex hulls. Info . Comput. 72 , 2 (1987), 150 \u2013 166 . Gregory J. E. Rawlins and Derick Wood. 1987. Optimal computation of finitely oriented convex hulls. Info. Comput. 72, 2 (1987), 150\u2013166.","journal-title":"Comput."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the International Conference on Emerging Technological Trends. 1\u20136.","author":"Saalima A.","unstructured":"A. Saalima and Dimple A. Shajahan . 2016. Shape reconstruction by analysing all the inner holes . In Proceedings of the International Conference on Emerging Technological Trends. 1\u20136. A. Saalima and Dimple A. Shajahan. 2016. Shape reconstruction by analysing all the inner holes. In Proceedings of the International Conference on Emerging Technological Trends. 1\u20136."},{"key":"e_1_2_1_49_1","unstructured":"Hanan Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.  Hanan Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00013-Y"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3173574.3173821"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.38"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.3390\/rs9060602"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/CISP.2010.5648277"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compenvurbsys.2016.01.003"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2016.1216995"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cageo.2017.08.008"}],"container-title":["ACM Transactions on Interactive Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431817","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3431817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:46Z","timestamp":1750195486000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3431817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,3]]},"references-count":56,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3431817"],"URL":"https:\/\/doi.org\/10.1145\/3431817","relation":{},"ISSN":["2160-6455","2160-6463"],"issn-type":[{"value":"2160-6455","type":"print"},{"value":"2160-6463","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,3]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}