{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T05:49:10Z","timestamp":1713419350848},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1997,6]]},"abstract":"<jats:p> In this paper we study several instances of the problem of determining the maximum number of topologically distinct two-dimensional images that three-dimensional scenes can induce. To bound this number, we investigate arrangements of curves and of surfaces that have a certain sparseness property. Given a collection of n algebraic surface patches of constant maximum degree in 3-space with the property that any vertical line stabs at most k of them, we show that the maximum combinatorial complexity of the entire arrangement that they induce is \u0398(n<jats:sup>2<\/jats:sup> k). We extend this result to collections of hypersurfaces in 4-space and to collections of (d &gt; 1)-simplices in d-space, for any fixed d. We show that this type of arrangements (sparse arrangements) is relevant to the study of the maximum number of topologically different views of a polyhedral terrain. For polyhedral terrains with n edges and vertices, we introduce a lower bound construction inducing \u03a9(n<jats:sup>5<\/jats:sup> \u03b1(n)) distinct views, and we present an almost matching upper bound. We then analyze the case of perspective views, point to the potential role of sparse arrangements in obtaining a sharp bound for this case, and present a lower bound construction inducing \u03a9(n<jats:sup>8<\/jats:sup>\u03b1(n)) distinct views. For the number of views of a collection of k convex polyhedra with a total of n faces, we show a bound of O(n<jats:sup>4<\/jats:sup> k<jats:sup>2<\/jats:sup>) for views from infinity and O(n<jats:sup>6<\/jats:sup> k<jats:sup>3<\/jats:sup>) for perspective views. We also present lower bound constructions for such scenes, with \u03a9(n<jats:sup>4<\/jats:sup> + n<jats:sup>2<\/jats:sup> k<jats:sup>4<\/jats:sup>) distinct views from infinity and \u03a9(n<jats:sup>6<\/jats:sup> + n<jats:sup>3<\/jats:sup> k<jats:sup>6<\/jats:sup>) views when the viewpoint can be anywhere in 3-space. <\/jats:p>","DOI":"10.1142\/s0218195997000120","type":"journal-article","created":{"date-parts":[[2003,10,16]],"date-time":"2003-10-16T10:47:26Z","timestamp":1066301246000},"page":"175-195","source":"Crossref","is-referenced-by-count":19,"title":["Sparse Arrangements and the Number of Views of Polyhedral Scenes"],"prefix":"10.1142","volume":"07","author":[{"given":"Mark de","family":"Berg","sequence":"first","affiliation":[{"name":"Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508 TB Utrecht, The Netherlands"}]},{"given":"Dan","family":"Halperin","sequence":"additional","affiliation":[{"name":"Robotics Laboratory, Department of Computer Science, Stanford University, Stanford, California 94305, USA"}]},{"given":"Mark","family":"Overmars","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508 TB Utrecht, The Netherlands"}]},{"given":"Marc van","family":"Kreveld","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508 TB Utrecht, The Netherlands"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195997000120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:30:55Z","timestamp":1565137855000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195997000120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,6]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1997,6]]}},"alternative-id":["10.1142\/S0218195997000120"],"URL":"https:\/\/doi.org\/10.1142\/s0218195997000120","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,6]]}}}