## An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains

In this paper, we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly. For example, our results apply directly to terrain maps. A distinguishing feature of our algorithm is that its running time is sensitive to the actual size of the visible image, rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is O((k + n) log2n) where n and k are, respectively, the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time of Ω(n2) irrespective of the output size. © 1995.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Numerical & Computational Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
- 0102 Applied Mathematics

### Citation

*Mathematical and Computer Modelling*,

*21*(5), 89–104. https://doi.org/10.1016/0895-7177(95)00016-U

*Mathematical and Computer Modelling*21, no. 5 (January 1, 1995): 89–104. https://doi.org/10.1016/0895-7177(95)00016-U.

*Mathematical and Computer Modelling*, vol. 21, no. 5, Jan. 1995, pp. 89–104.

*Scopus*, doi:10.1016/0895-7177(95)00016-U.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- Numerical & Computational Mathematics
- 4903 Numerical and computational mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0103 Numerical and Computational Mathematics
- 0102 Applied Mathematics