1. A Space-Optimal Hidden Surface Removal Algorithm for Iso-Oriented Rectangles
- Author
-
Andreas Kosmatopoulos, Athanasios K. Tsakalidis, and Kostas Tsichlas
- Subjects
Computer graphics ,Computer science ,Hidden surface determination ,Computer Science (miscellaneous) ,Space (mathematics) ,Computational geometry ,Algorithm - Abstract
We investigate the problem of finding the visible pieces of a scene of objects from a specified viewpoint. In particular, we are interested in the design of an efficient hidden surface removal algorithm for a scene comprised of iso-oriented rectangles. We propose an algorithm where given a set of [Formula: see text] iso-oriented rectangles we report all visible surfaces in [Formula: see text] time and linear space, where [Formula: see text] is the number of surfaces reported. The previous best result by Bern [Journal of Computer and System Sciences 40 (1990) 49–69], has the same time complexity but uses [Formula: see text] space.
- Published
- 2020