Worst-case versus average case complexity of ray-shooting
Worst-case versus average case complexity of ray-shooting
复制标题
射线射击的最坏情况与平均情况复杂性
作者：
László Szirmay;G. Márton
本文研究了射线射击算法的最坏情况和平均情况复杂性度量，以便找到为什么计算机图形从业者更喜欢启发式方法而不是广泛研究最坏情况最优算法的问题的答案。它证明了射线射击在最坏情况下至少需要对数时间，并讨论了如何设计这种最坏情况最优算法的策略。它还检查了对数时间算法的存储复杂性的下限，并得出结论：就所需存储而言，对数时间的成本非常高。为了找到平均情况的度量，建立了场景的概率模型。我们得出的结论是，针对平均情况优化的算法不仅更容易实现，而且具有适度的存储要求，甚至可以针对大多数问题运行得更快。
This paper examines worst-case and average-case complexity measures of ray-shooting algorithms in order to find the answer to the question why computer graphics practitioners prefer heuristic methods to extensively studied worst-case optimal algorithms. It demonstrates that ray-shooting requires at least logarithmic time in the worst-case and discusses the strategies how to design such worst-case 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. In order to find average-case measures, a probabilistic model of the scene is established. We conclude that algorithms optimized for the average-case are not only much simpler to implement, but have moderate storage requirement and can even run faster for the majority of problems.