Abstract
We show that the number of topologically different orthographic views of a polyhedral terrain withn edges isO(n 5+ɛ), and that the number of topologically different perspective views of such a terrain isO(n 8+ɛ), for any ɛ>0. Both bounds are almost tight in the worst case. The proofs are simple consequences of the recent almost-tight bounds of [11] on the complexity of lower envelopes in higher dimensions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. de Berg, D. Halperin, M. Overmars, and M. van Kreveld, Sparse arrangements and the number of views of polyhedral scenes, Manuscript, 1991.
K. Bowyer and C. Dyer, Aspect graphs: An introduction and survey of recent results,Internat. J. Imaging Systems Technol. 2 (1990), 315–328.
I. Chakravarty and H. Freeman, Characteristic views as a basis for three-dimensional object recognition,Proc. SPIE: Robot Vision 336 (1982), 37–45.
R. Cole and M. Sharir, Visibility problems for polyhedral terrains,J. Symbolic Comput. 7 (1990), 11–30.
C. Crawford, Aspect graphs and robot vision,Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 1985, pp. 382–384.
Z. Gigus, J. Canny, and R. Seidel, Efficiently computing and representing aspect graphs of polyhedral objects,IEEE Trans. Pattern Anal. Macli. Intell. 13 (1991), 542–551.
D. Halperin and M. Sharir, New bounds for lower envelopes in three dimensions with applications to visibility in terrains,Proc. 9th ACM Symp. on Computational Geometry, 1993, pp. 11–18.
J. Koenderink and A. van Doorn, The singularities of visual mapping,Biol. Cybernat. 24 (1976), 51–59.
W. Plantinga and C. Dyer, An algorithm for constructing the aspect graph,Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 123–131.
W. Plantinga and C. Dyer, Visibility, occlusion, and the aspect graph,Internat. J. Comput. Vision 5 (1990), 137–160.
M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 498–507.
J. Snoeyink, The number of views of axis-parallel objects,Algorithms Rev. 2 (1991), 27–32.
Author information
Authors and Affiliations
Additional information
Pankaj Agarwal has been supported by National Science Foundation Grant CCR-91-06514. Micha Sharir has been supported by National Science Foundation Grant CCR-91-22103, and by grants from the U.S.—Israeli Binational Science Foundation, the G.I.F.—the German Israeli Foundation for Scientific Research and Development- and the Fund for Basic Research administered by the Israeli Academy of Sciences.
Rights and permissions
About this article
Cite this article
Agarwal, P.K., Sharir, M. On the number of views of polyhedral terrains. Discrete Comput Geom 12, 177–182 (1994). https://doi.org/10.1007/BF02574373
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574373