Worst-case versus average case complexity of ray-shooting (Q1271535)

The theoretically best algorithms (in terms of computational complexity) for ray shooting to determine the illumination of objects from a point source of light are practically unworkable because their memory storage requirements exceed the possible. The author discuss a general method of judging heuristic method as to complexity of preprocessing and the algorithm itself, as well as storage requirements. They find that for most of the algorithms in use, the practical implementation does not reach the lower limits predicted by the theory. They show that of these heuristic algorithms, a divide-and-conquer algorithm based on an ordering of objects by the distance from the source of light, is the best in the average case since it works in \(O(n\log n)\) time and, alone among the methods, needs only \(O(n)\) storage in practical implementation.