Worst-case versus average case complexity of ray-shooting

DOI10.1007/BF02684409MaRDI QIDQ1271535zbMATH OpenFDO

Publication date 26 April 1999

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02684409

algorithms average case computational complexity divide-and-conquer algorithm illumination of objects ray shooting worst-case

Mathematics Subject Classification ID

Descriptive geometry (51N05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Review text

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.

Recommendations

Cites work

Cited in

(2)

Describes a project that uses

Uses Software

ARVO

This page was built for publication: Worst-case versus average case complexity of ray-shooting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1271535)