On the Limitations of Worst-case Optimal Ray Shooting Algorithms

Szirmay-Kalos László, Márton Gábor
Department of Process Control, Technical University of Budapest,
Budapest, Muegyetem rkp. 11, H-1111, HUNGARY


This paper examines the lower-bounds of worst-case complexity measures of ray-shooting algorithms. It demonstrates that ray-shooting requires at least logarithmic time and discusses the strategies how to design such optimal algorithms. It also examines the lower-bounds of storage complexity of logarithmic-time algorithms and concludes that logarithmic time has very high price in terms of required storage.


Ray-shooting, complexity analysis, data-stuctures.