{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:02:44Z","timestamp":1758268964358,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T00:00:00Z","timestamp":1531872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1533823"],"award-info":[{"award-number":["1533823"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>\n            Let\n            <jats:italic>T<\/jats:italic>\n            be a terrain and\n            <jats:italic>P<\/jats:italic>\n            be a set of points on its surface. An important problem in Geographic Information Science (GIS) is computing the\n            <jats:italic>visibility index<\/jats:italic>\n            of a point\n            <jats:italic>p<\/jats:italic>\n            on\n            <jats:italic>P<\/jats:italic>\n            , that is, the number of points in\n            <jats:italic>P<\/jats:italic>\n            that are visible from\n            <jats:italic>p<\/jats:italic>\n            . The\n            <jats:italic>total visibility-index<\/jats:italic>\n            problem asks for the visibility index of\n            <jats:italic>every<\/jats:italic>\n            point in\n            <jats:italic>P<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            We present the first subquadratic-time algorithm to solve the one-dimensional total-visibility-index problem. Our algorithm uses a geometric dualization technique to reduce the problem to a set of instances of the red--blue line segment intersection counting problem, allowing us to find the total visibility-index in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time. We implement a naive\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) approach and four variations of our algorithm: one that uses an existing red--blue line segment intersection counting algorithm and three new approaches that leverage features specific to our problem. Two of our implementations allow for parallel execution, requiring\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) work in the CREW PRAM model.\n          <\/jats:p>\n          <jats:p>We present experimental results for both serial and parallel implementations on synthetic and real-world datasets using two hardware platforms. Results show that all variants of our algorithm outperform the naive approach by several orders of magnitude. Furthermore, we show that our special-case red--blue line segment intersection counting implementations out-perform the existing general-case solution by up to a factor 10. Our fastest parallel implementation is able to process a terrain of more than 100 million vertices in under 3 minutes, achieving up to 85% parallel efficiency using 16 cores.<\/jats:p>","DOI":"10.1145\/3209685","type":"journal-article","created":{"date-parts":[[2018,7,16]],"date-time":"2018-07-16T13:25:21Z","timestamp":1531747521000},"page":"1-23","source":"Crossref","is-referenced-by-count":2,"title":["An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization"],"prefix":"10.1145","volume":"23","author":[{"given":"Peyman","family":"Afshani","sequence":"first","affiliation":[{"name":"MADALGO, Aarhus University, Aarhus, Denmark"}]},{"given":"Mark De","family":"Berg","sequence":"additional","affiliation":[{"name":"TU Eindhoven, MB Eindhoven, The Netherlands"}]},{"given":"Henri","family":"Casanova","sequence":"additional","affiliation":[{"name":"University of Hawaii at Manoa, Honolulu, HI, USA"}]},{"given":"Ben","family":"Karsin","sequence":"additional","affiliation":[{"name":"University of Hawaii at Manoa, Honolulu, HI, USA"}]},{"given":"Colin","family":"Lambrechts","sequence":"additional","affiliation":[{"name":"TU Eindhoven, MB Eindhoven, The Netherlands"}]},{"given":"Nodari","family":"Sitchinava","sequence":"additional","affiliation":[{"name":"University of Hawaii at Manoa, Honolulu, HI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2823-6827","authenticated-orcid":false,"given":"Constantinos","family":"Tsirogiannis","sequence":"additional","affiliation":[{"name":"MADALGO, Aarhus University, Aarhus, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2018,7,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"ArcGIS. 2016. Retrieved from http:\/\/www.esri.com\/software\/arcgis.  ArcGIS. 2016. Retrieved from http:\/\/www.esri.com\/software\/arcgis."},{"key":"e_1_2_1_2_1","unstructured":".GRASS (Geographic Resources Analysis Support System). 2016. Retrieved from https:\/\/grass.osgeo.org.  .GRASS (Geographic Resources Analysis Support System). 2016. Retrieved from https:\/\/grass.osgeo.org."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/195613.195617"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997825"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/17538947.2011.555565"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187875"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12142"},{"volume-title":"Proceedings of the Symposium on GeoInformatics (GeoInfo\u201913)","author":"Ferreira C.","key":"e_1_2_1_9_1","unstructured":"C. Ferreira , M. V. Andrade , S. V. Magalhaes , W. R. Franklin , and G. C. Pena . 2013. A parallel sweep line algorithm for visibility computation . In Proceedings of the Symposium on GeoInformatics (GeoInfo\u201913) . 85--96. C. Ferreira, M. V. Andrade, S. V. Magalhaes, W. R. Franklin, and G. C. Pena. 2013. A parallel sweep line algorithm for visibility computation. In Proceedings of the Symposium on GeoInformatics (GeoInfo\u201913). 85--96."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424398"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653791"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1068\/b12979"},{"volume-title":"Proceedings of Advances in GIS Research: 6th International Symposium on Spatial Data Handling. 751--770","author":"Franklin W. R.","key":"e_1_2_1_13_1","unstructured":"W. R. Franklin and C. K. Ray . 1994. Higher isn\u2019t necessarily better: Visibility algorithms and experiments . In Proceedings of Advances in GIS Research: 6th International Symposium on Spatial Data Handling. 751--770 . W. R. Franklin and C. K. Ray. 1994. Higher isn\u2019t necessarily better: Visibility algorithms and experiments. In Proceedings of Advances in GIS Research: 6th International Symposium on Spatial Data Handling. 751--770."},{"key":"e_1_2_1_14_1","first-page":"256","article-title":"The continuous 1.5D terrain guarding problem: Descretization, optimal solutions, and PTAS","volume":"7","author":"Friedrichs S.","year":"2016","unstructured":"S. Friedrichs , M. Hemmer , J. King , and C. Schmidt . 2016 . The continuous 1.5D terrain guarding problem: Descretization, optimal solutions, and PTAS . J. Comput. Geom. 7 , 1 (2016), 256 -- 284 . S. Friedrichs, M. Hemmer, J. King, and C. Schmidt. 2016. The continuous 1.5D terrain guarding problem: Descretization, optimal solutions, and PTAS. J. Comput. Geom. 7, 1 (2016), 256--284.","journal-title":"J. Comput. Geom."},{"volume-title":"Proceedings of the 31st European Workshop on Computational Geometry. 216--219","author":"Haas A.","key":"e_1_2_1_15_1","unstructured":"A. Haas and M. Hemmer . 2015. Efficient algorithms and implementations for visibility in 1.5D terrains . In Proceedings of the 31st European Workshop on Computational Geometry. 216--219 . A. Haas and M. Hemmer. 2015. Efficient algorithms and implementations for visibility in 1.5D terrains. In Proceedings of the 31st European Workshop on Computational Geometry. 216--219."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646513.695510"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412233"},{"key":"e_1_2_1_18_1","first-page":"04","article-title":"Terrain visibility with multiple viewpoints","volume":"24","author":"Hurtado F.","year":"2014","unstructured":"F. Hurtado , M. L\u00f6ffler , I. Matos , V. Sacrist\u00e1n , M. Saumell , R. Silveira , and F. Staals . 2014 . Terrain visibility with multiple viewpoints . Int. J. Comput. Geom. App. 24 , 04 (Dec. 2014). F. Hurtado, M. L\u00f6ffler, I. Matos, V. Sacrist\u00e1n, M. Saumell, R. Silveira, and F. Staals. 2014. Terrain visibility with multiple viewpoints. Int. J. Comput. Geom. App. 24, 04 (Dec. 2014).","journal-title":"Int. J. Comput. Geom. App."},{"key":"e_1_2_1_19_1","volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e1J\u00e1 J.","unstructured":"J. J\u00e1J\u00e1 . 1992. An Introduction to Parallel Algorithms ( 1 st ed.). Addison Wesley . J. J\u00e1J\u00e1. 1992. An Introduction to Parallel Algorithms (1st ed.). Addison Wesley.","edition":"1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009740712769"},{"volume-title":"Proceedings of Beyond the Artifact: Digital Interpretation of the Past: The 32nd Computer Applications and Quantitative Methods in Archaeology Conference (CAA\u201904)","author":"Llobera M.","key":"e_1_2_1_21_1","unstructured":"M. Llobera , D. Wheatley , J. Steele , S. Cox , and O. Parchment . 2004. Calculating the inherent visual structure of a landscape (inherent viewshed) using high-throughput computing . In Proceedings of Beyond the Artifact: Digital Interpretation of the Past: The 32nd Computer Applications and Quantitative Methods in Archaeology Conference (CAA\u201904) . 146--151. M. Llobera, D. Wheatley, J. Steele, S. Cox, and O. Parchment. 2004. Calculating the inherent visual structure of a landscape (inherent viewshed) using high-throughput computing. In Proceedings of Beyond the Artifact: Digital Interpretation of the Past: The 32nd Computer Applications and Quantitative Methods in Archaeology Conference (CAA\u201904). 146--151."},{"volume-title":"Proceedingsf of the 30th European Workshop on Computational Geometry.","author":"L\u00f6ffler M.","key":"e_1_2_1_22_1","unstructured":"M. L\u00f6ffler , M. Saumell , and R. I. Silveira . 2014. A faster algorithm to compute the visibility map of a 1.5 D terrain . In Proceedingsf of the 30th European Workshop on Computational Geometry. M. L\u00f6ffler, M. Saumell, and R. I. Silveira. 2014. A faster algorithm to compute the visibility map of a 1.5 D terrain. In Proceedingsf of the 30th European Workshop on Computational Geometry."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/cgip.1994.1027"},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"Efficient data structure and highly scalable algorithm for total-viewshed computation","volume":"8","author":"Tabik S.","year":"2014","unstructured":"S. Tabik , A. Cervilla , E. Zapata , and L. Romero . 2014 . Efficient data structure and highly scalable algorithm for total-viewshed computation . IEEE J. Select. Top. Appl. Earth Observ. Remote Sens. 8 , 1 (2014), 1 -- 7 . S. Tabik, A. Cervilla, E. Zapata, and L. Romero. 2014. Efficient data structure and highly scalable algorithm for total-viewshed computation. IEEE J. Select. Top. Appl. Earth Observ. Remote Sens. 8, 1 (2014), 1--7.","journal-title":"IEEE J. Select. Top. Appl. Earth Observ. Remote Sens."},{"volume-title":"CGAL User and Reference Manual (4.11 ed.)","author":"Project CGAL","key":"e_1_2_1_25_1","unstructured":"The CGAL Project . 2017. CGAL User and Reference Manual (4.11 ed.) . CGAL Editorial Board. Retrieved from http:\/\/doc.cgal.org\/4.11\/Manual\/packages.html The CGAL Project. 2017. CGAL User and Reference Manual (4.11 ed.). CGAL Editorial Board. Retrieved from http:\/\/doc.cgal.org\/4.11\/Manual\/packages.html"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 7th International Symposium on Spatial Data Handling. 13--15","author":"van Kreveld M.","year":"1996","unstructured":"M. van Kreveld . 1996 . Variations on sweep algorithms: Efficient computation of extended viewsheds and class intervals . In Proceedings of the 7th International Symposium on Spatial Data Handling. 13--15 . M. van Kreveld. 1996. Variations on sweep algorithms: Efficient computation of extended viewsheds and class intervals. In Proceedings of the 7th International Symposium on Spatial Data Handling. 13--15."},{"volume-title":"Cumulative Viewshed Analysis: A GIS-based Method for Investigating Intervisibility and Its Archaeological Application","author":"Wheatley D.","key":"e_1_2_1_27_1","unstructured":"D. Wheatley . 1995. Cumulative Viewshed Analysis: A GIS-based Method for Investigating Intervisibility and Its Archaeological Application . Routlege , London . D. Wheatley. 1995. Cumulative Viewshed Analysis: A GIS-based Method for Investigating Intervisibility and Its Archaeological Application. Routlege, London."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2012.692372"},{"key":"e_1_2_1_29_1","volume-title":"Technical Report 122. International","author":"Zomer R. J.","year":"2007","unstructured":"R. J. Zomer , D. A. Bossio , A. Trabucco , L. Yuanjie , D. C. Gupta , and V. P. Singh . 2007 . Trees and Water: Smallholder Agroforestry on Irrigated Lands in Northern India. Technical Report 122. International Water Management Institute, Colombo, Sri Lanka . 45 pages. R. J. Zomer, D. A. Bossio, A. Trabucco, L. Yuanjie, D. C. Gupta, and V. P. Singh. 2007. Trees and Water: Smallholder Agroforestry on Irrigated Lands in Northern India. Technical Report 122. International Water Management Institute, Colombo, Sri Lanka. 45 pages."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.agee.2008.01.014"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209685","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:33Z","timestamp":1750210773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,18]]},"references-count":30,"alternative-id":["10.1145\/3209685"],"URL":"https:\/\/doi.org\/10.1145\/3209685","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2018,7,18]]}}}