{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:31:49Z","timestamp":1767918709501,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,6,21]],"date-time":"2017-06-21T00:00:00Z","timestamp":1498003200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["9085\/13-0"],"award-info":[{"award-number":["9085\/13-0"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1117277"],"award-info":[{"award-number":["IIS-1117277"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004901","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de Minas Gerais","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004901","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2016,7]]},"abstract":"<jats:p>\n                    This article presents T\n                    <jats:sc>iled<\/jats:sc>\n                    VS, a fast external algorithm and implementation for computing viewsheds. T\n                    <jats:sc>iled<\/jats:sc>\n                    VS is intended for terrains that are too large for internal memory, even more than 100,000\u00d7100,000 points. It subdivides the terrain into tiles that are stored compressed on disk and then paged into memory with a custom cache data structure and least recently used algorithm. If there is sufficient available memory to store a whole row of tiles, which is easy, then this specialized data management is faster than relying on the operating system\u2019s virtual memory management. Applications of viewshed computation include siting radio transmitters, surveillance, and visual environmental impact measurement.\n                  <\/jats:p>\n                  <jats:p>\n                    T\n                    <jats:sc>iled<\/jats:sc>\n                    VS runs a rotating line of sight from the observer to points on the region boundary. For each boundary point, it computes the visibility of all terrain points close to the line of sight. The running time is linear in the number of points. No terrain tile is read more than twice. T\n                    <jats:sc>iled<\/jats:sc>\n                    VS is very fast, for instance, processing a 104,000\u00d7104,000 terrain on a modest computer with only 512MB of RAM took only 1\u00bd hours. On large datasets, T\n                    <jats:sc>iled<\/jats:sc>\n                    VS was several times faster than competing algorithms, such as the ones included in GRASS. The source code of T\n                    <jats:sc>iled<\/jats:sc>\n                    VS is freely available for nonprofit researchers to study, use, and extend.\n                  <\/jats:p>\n                  <jats:p>A preliminary version of this algorithm appeared in a four-page ACM SIGSPATIAL GIS 2012 conference paper, \u201cMore Efficient Terrain Viewshed Computation on Massive Datasets Using External Memory.\u201d This more detailed version adds the fast lossless compression stage that reduces the time by 30% to 40%, and many more experiments and comparisons.<\/jats:p>","DOI":"10.1145\/2903206","type":"journal-article","created":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T09:02:27Z","timestamp":1466672547000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient External Memory Algorithm for Terrain Viewshed Computation"],"prefix":"10.1145","volume":"2","author":[{"given":"Chaulio R.","family":"Ferreira","sequence":"first","affiliation":[{"name":"DPI Federal University of Vi\u00e7osa, Brazil, MG, Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus V. A.","family":"Andrade","sequence":"additional","affiliation":[{"name":"DPI Federal University of Vi\u00e7osa, Brazil, MG, Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Salles V. G.","family":"Magalh\u00e3es","sequence":"additional","affiliation":[{"name":"DPI Federal University of Vi\u00e7osa, Brazil, MG, Brasil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W. Randolph","family":"Franklin","sequence":"additional","affiliation":[{"name":"Rensselaer Polytechnic Institute, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-014-0936-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-009-0100-9"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 30th European Workshop on Computational Geometry (EuroCG\u201914)","author":"Arkin Esther M.","unstructured":"Esther M. Arkin, Alon Efraty, and Joseph S. B. Mitchell. 2014. Hybrid algorithms for scheduling sensors for guarding polygonal domains. In Proceedings of the 30th European Workshop on Computational Geometry (EuroCG\u201914)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-007-9015-5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/646719.702219"},{"key":"e_1_2_1_7_1","first-page":"612","article-title":"Viewsheds: A complementary management approach to buffer zones","volume":"25","author":"Camp Richard J.","year":"1997","unstructured":"Richard J. Camp, David T. Sinton, and Richard L. Knight. 1997. Viewsheds: A complementary management approach to buffer zones. Wildlife Society Bulletin 25, 3, 612--615.","journal-title":"Wildlife Society Bulletin"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 23rd Army Science Conference.","author":"Danny","unstructured":"Danny C. Champion and John E. Lavery. 2002. Line of sight in natural terrain determined by L1-spline and conventional methods. In Proceedings of the 23rd Army Science Conference."},{"key":"e_1_2_1_9_1","volume-title":"Retrieved","author":"Collet Yann","year":"2012","unstructured":"Yann Collet. 2012. Extremely Fast Compression Algorithm. Retrieved May 20, 2016, from https:\/\/github.com\/Cyan4973\/lz4."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50008-5"},{"key":"e_1_2_1_11_1","volume-title":"Retrieved","author":"Dell Inc.","year":"2016","unstructured":"Dell Inc. 2016. Dell Chromebook 11. Retrieved May 20, 2016, from http:\/\/www.dell.com\/us\/p\/chromebook-11-3120\/pd?ref&equals;PD_OC."},{"key":"e_1_2_1_12_1","series-title":"Lecture Notes from the EEF Summer School on Massive Data Sets. BRICS","volume-title":"Cache-oblivious algorithms and data structures","author":"Demaine Erik D.","unstructured":"Erik D. Demaine. 2002. Cache-oblivious algorithms and data structures. In Lecture Notes from the EEF Summer School on Massive Data Sets. BRICS, University of Aarhus, Denmark, 1--29."},{"key":"e_1_2_1_13_1","volume-title":"STXXL : Standard Template Library for XXL Data Sets. Technical Report. Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe","author":"Dementiev Roman","year":"2005","unstructured":"Roman Dementiev, Lutz Kettner, and Peter Sanders. 2005. STXXL : Standard Template Library for XXL Data Sets. Technical Report. Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe. http:\/\/stxxl.sourceforge.net\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525355"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00255-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2424321.2424398"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/02693799308901965"},{"key":"e_1_2_1_18_1","first-page":"1297","article-title":"Extending the applicability of viewsheds in landscape planning","volume":"62","author":"Fisher Peter F.","year":"1996","unstructured":"Peter F. Fisher. 1996. Extending the applicability of viewsheds in landscape planning. Photogrammetric Engineering and Remote Sensing 62, 11, 1297--1302.","journal-title":"Photogrammetric Engineering and Remote Sensing"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653791"},{"key":"e_1_2_1_20_1","volume-title":"Advances in GIS Research: 6th International Symposium on Spatial Data Handling, T. C. Waugh and R. G. Healey (Eds.). Taylor & Francis","author":"Randolph Franklin W.","year":"1994","unstructured":"W. Randolph Franklin and Clark Ray. 1994. Higher isn\u2019t necessarily better: Visibility algorithms and experiments. In Advances in GIS Research: 6th International Symposium on Spatial Data Handling, T. C. Waugh and R. G. Healey (Eds.). Taylor & Francis, Edinburgh, Scotland, 751--770."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-35589-8_52"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071383"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02097802"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2525314.2525369"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1412233"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195914600085"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/584458.584487"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0198-9715(98)00012-X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666310.2666394"},{"key":"e_1_2_1_30_1","first-page":"1461","article-title":"Modeling the effect of data errors on feature extraction from digital elevation models","volume":"58","author":"Lee Jay","year":"1992","unstructured":"Jay Lee, Peter K. Snyder, and Peter F. Fisher. 1992. Modeling the effect of data errors on feature extraction from digital elevation models. Photogrammetric Engineering and Remote Sensing 58, 10, 1461--1467.","journal-title":"Photogrammetric Engineering and Remote Sensing"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/136588198241554"},{"key":"e_1_2_1_32_1","volume-title":"Digital Terrain Modeling\u2014Principles and Methodology","author":"Li Zhilin","unstructured":"Zhilin Li, Qing Zhu, and Christopher Gold. 2005. Digital Terrain Modeling\u2014Principles and Methodology. CRC Press, Boca Raton, FL."},{"key":"e_1_2_1_33_1","first-page":"143","article-title":"Multiple observer siting in huge terrains stored in external memory","volume":"3","author":"Magalh\u00e3es Salles V. G.","year":"2011","unstructured":"Salles V. G. Magalh\u00e3es, Marcus V. A. Andrade, and W. Randolph Franklin. 2011. Multiple observer siting in huge terrains stored in external memory. International Journal of Computer Information Systems and Industrial Management 3, 143--149. http:\/\/www.mirlabs.org\/ijcisim\/volume1.html.","journal-title":"International Journal of Computer Information Systems and Industrial Management"},{"key":"e_1_2_1_34_1","first-page":"1293","article-title":"An accuracy assessment of various GIS-based viewshed delineation techniques","volume":"67","author":"Maloy Mark A.","year":"2001","unstructured":"Mark A. Maloy and Denls J. Dean. 2001. An accuracy assessment of various GIS-based viewshed delineation techniques. Photogrammetric Engineering and Remote Sensing 67, 11, 1293--1298.","journal-title":"Photogrammetric Engineering and Remote Sensing"},{"key":"e_1_2_1_35_1","volume-title":"Retrieved","author":"MindSites Group","year":"2016","unstructured":"MindSites Group. 2016. USGS SDTS Format Digital Elevation Model Data (DEM). Retrieved May 20, 2016, from http:\/\/data.geocomm.com\/dem\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(94)90002-7"},{"key":"e_1_2_1_37_1","volume-title":"Retrieved","author":"National Digital Elevation Program.","year":"2015","unstructured":"National Digital Elevation Program. 2015. Digital Elevation Glossary of Terms. Retrieved May 20, 2016, from http:\/\/www.ndep.gov\/glossary.html."},{"key":"e_1_2_1_38_1","volume-title":"Retrieved","author":"Software Passmark","year":"2013","unstructured":"Passmark Software. 2013. CPU Benchmarks. Retrieved May 20, 2016, from http:\/\/www.cpubenchmark.net\/."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370911"},{"key":"e_1_2_1_40_1","first-page":"77","article-title":"Shortest path to a segment and quickest visibility queries","volume":"07","author":"Polishchuk Valentin","year":"2016","unstructured":"Valentin Polishchuk, Esther M. Arkin, Alon Efrat, Christian Knauer, Joseph S. B. Mitchell, Guenter Rote, Lena Schlipf, Topi Talvitie, and Valentin Polishchuk. 2016. Shortest path to a segment and quickest visibility queries. Journal of Computational Geometry 07, 02, 77--100. http:\/\/jocg.org\/index.php\/jocg\/article\/view\/264.","journal-title":"Journal of Computational Geometry"},{"key":"e_1_2_1_41_1","volume-title":"Retrieved","author":"Rabus Bernhard","year":"2003","unstructured":"Bernhard Rabus, Michael Eineder, Achim Roth, and Richard Bamler. 2003. Shuttle Radar Topography Mission. Retrieved May 20, 2016, from http:\/\/www2.jpl.nasa.gov\/srtm\/."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/221733"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.764870"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 15th International Conference on Enterprise Information Systems (ICEIS\u201913)","author":"Silveira Jaqueline A.","unstructured":"Jaqueline A. Silveira, Salles V. G. Magalh\u00e3es, Marcus V. A. Andrade, and Vinicius S. Concei\u00e7\u00e3o. 2013. A library to support the development of applications that process huge matrices in external memory. In Proceedings of the 15th International Conference on Enterprise Information Systems (ICEIS\u201913). 305--310."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463434.1463456"},{"key":"e_1_2_1_46_1","volume-title":"Retrieved","author":"Toma Laura","year":"2010","unstructured":"Laura Toma, Yi Zhuang, and William Richard. 2010. R.viewshed. Retrieved May 20, 2016, from https:\/\/trac.osgeo.org\/grass\/browser\/grass-addons\/raster\/r.viewshed?rev&equals;45442."},{"key":"e_1_2_1_47_1","volume-title":"Retrieved","author":"Guide Tom\u2019s","year":"2016","unstructured":"Tom\u2019s Guide. 2016. Smartphones Buying Guide. Retrieved May 20, 2016, from http:\/\/www.tomsguide.com\/us\/smartphone-buying-guide,review-1971.html."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 7th International Symposium on Spatial Data Handling. 13--15","author":"Kreveld Marc Van","year":"1996","unstructured":"Marc 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."}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903206","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2903206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:29:30Z","timestamp":1763458170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2903206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,21]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["10.1145\/2903206"],"URL":"https:\/\/doi.org\/10.1145\/2903206","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,21]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-03-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}