{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T09:37:54Z","timestamp":1648633074204},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p> A polyhedral terrain is the graph of a continuous piecewise linear function defined over the triangles of a triangulation in the xy-plane. Two points on or above a terrain are visible to each other if the line-of-sight does not intersect the space below the terrain. In this paper, we look at three related visibility problems in terrains. Suppose we are given a terrain T with n triangles and two regions R<jats:sub>1<\/jats:sub> and R<jats:sub>2<\/jats:sub> on T, i.e., two simply connected subsets of at most m triangles. First, we present an algorithm that determines, for any constant \u220a &gt; 0, within O(n<jats:sup>1+\u220a<\/jats:sup>m) time and storage whether or not R<jats:sub>1<\/jats:sub> and R<jats:sub>2<\/jats:sub> are completely intervisible. We also give an O(m<jats:sup>3<\/jats:sup>n<jats:sup>4<\/jats:sup>) time algorithm to determine whether every point in R<jats:sub>1<\/jats:sub> sees at least one point in R<jats:sub>2<\/jats:sub>. Finally, we present an O(m<jats:sup>2<\/jats:sup>n<jats:sup>2<\/jats:sup> log n) time algorithm to determine whether there exists a pair of points p \u2208 R<jats:sub>1<\/jats:sub> and q \u2208 R<jats:sub>2<\/jats:sub>, such that p and q see each other. <\/jats:p>","DOI":"10.1142\/s0218195907002367","type":"journal-article","created":{"date-parts":[[2007,8,21]],"date-time":"2007-08-21T09:39:24Z","timestamp":1187689164000},"page":"331-347","source":"Crossref","is-referenced-by-count":1,"title":["REGION INTERVISIBILITY IN TERRAINS"],"prefix":"10.1142","volume":"17","author":[{"given":"ESTHER","family":"MOET","sequence":"first","affiliation":[{"name":"Department of Information and Computing Sciences, Universiteit Utrecht, P.O.Box 80.089, 3508 TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARC","family":"VAN KREVELD","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Universiteit Utrecht, P.O.Box 80.089, 3508 TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"REN\u00c9","family":"VAN OOSTRUM","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Universiteit Utrecht, P.O.Box 80.089, 3508 TB Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(89)80003-3"},{"key":"rf2","unstructured":"L.\u00a0De Floriani and P.\u00a0Magillo, Geographic Information Systems: Principles, Techniques, Managament and Applications, eds. P. A.\u00a0Longley (John Wiley & Sons, 1999)\u00a0pp. 543\u2013556."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.07.008"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90024-M"},{"key":"rf10","first-page":"33","volume":"3","author":"Fisher P. F.","journal-title":"Geogr. Syst."},{"key":"rf12","first-page":"1129","volume":"28","author":"Sorensen P.","journal-title":"Photogramm. Eng. Rem. Sens."},{"key":"rf14","first-page":"413","volume":"5","author":"Lee J.","journal-title":"Int. J. Geogr. Inform. Syst."},{"key":"rf15","first-page":"331","volume":"7","author":"Fisher P. F.","journal-title":"Int. J. Geogr. Inform. Syst."},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.005"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187019"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8"},{"key":"rf23","unstructured":"D.\u00a0Mount, Handbook of Discrete and Computational Geometry, eds. J. E.\u00a0Goodman and J.\u00a0O'Rourke (CRC Press LLC, Boca Raton, FL, 1997)\u00a0pp. 615\u2013632."},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955043"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90062-5"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90005-2"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/BF00337644"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195997000120"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574373"},{"key":"rf32","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"Mulmuley K.","year":"1993"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195907002367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:30:07Z","timestamp":1565137807000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195907002367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":21,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1142\/S0218195907002367"],"URL":"https:\/\/doi.org\/10.1142\/s0218195907002367","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]}}}