ON THE NUMBER OF VIEWS OF POLYHEDRAL TERRAINS

Authors
AGARWAL PK SHARIR M
Citation
Pk. Agarwal et M. Sharir, ON THE NUMBER OF VIEWS OF POLYHEDRAL TERRAINS, Discrete & computational geometry, 12(2), 1994, pp. 177-182
Citations number
12
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
12
Issue
2
Year of publication
1994
Pages
177 - 182
Database
ISI
SICI code
0179-5376(1994)12:2<177:OTNOVO>2.0.ZU;2-X
Abstract
We show that the number of topologically different orthographic views of a polyhedral terrain with n edges is O(n5+epsilon), and that the nu mber of topologically different perspective views of such a terrain is O(n8+epsilon), for any epsilon > 0. Both bounds are almost tight in t he worst case. The proofs are simple consequences of the recent almost -tight bounds of [11] on the complexity of lower envelopes in higher d imensions.