Szirmay-Kalos László, Márton Gábor
Department of Process Control, Technical University of Budapest,
Budapest, Muegyetem rkp. 11, H-1111, HUNGARY
szirmay@fsz.bme.hu
Abstract:
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.
Keywords:
Ray-shooting, complexity analysis, data-stuctures.