A Space-Optimal Hidden Surface Removal Algorithm for Iso-Oriented Rectangles
Ανδρέας Κοσματόπουλος, Athanasios Tsakalidis, Kostas Tsichlas · International Journal of Foundations of Computer Science · 2020
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.