On The Computational Complexity Of Hierarchical Radiosity
Robert Garmann, Heinrich Müller:
On The Computational Complexity Of Hierarchical Radiosity,
in: Computer Science in Perspective - Essays
Dedicated to Thomas Ottmann, R. Klein, H.-W. Six, L. Wegner (eds.),
LNCS 2598, Springer-Verlag, Berlin, 2003, 167-178
The hierarchical radiosity algorithm is an efficient approach
to simulation of light with the goal of photo-realistic image
rendering. Hanrahan et. al.
describe the initialization and the refinement of links between
the scene's patches based upon a user-specified error parameter
They state that the number of links is linear in the number
of elements if Fe is assumed to be a constant.
We present a result based upon the assumption that
the geometry is constant and Fe approaches 0 in
Then the algorithm generates L = Theta(N2) links where
N denotes the number of elements generated by the algorithm.