Worst-case versus average case complexity of ray-shooting
type: Item
instance of: scholarly article
title: Worst-case versus average case complexity of ray-shooting
zbMATH Open document ID: 0911.65150
DOI: 10.1007/BF02684409
author: K. Appert
published in: Computing
publication date: 1999-04-26T00:00:00Z
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.
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 51N05
zbMATH DE Number: 1220840
zbMATH Keywords: worst-case
zbMATH Keywords: average case
zbMATH Keywords: algorithms
zbMATH Keywords: computational complexity
zbMATH Keywords: ray shooting
zbMATH Keywords: illumination of objects
zbMATH Keywords: divide-and-conquer algorithm
reviewed by: Heinrich Guggenheimer
describes a project that uses: ARVO
MaRDI profile type: Publication
cites work: On the complexity of computations under varying sets of primitives
cites work: Q4692930
cites work: Q4076577
cites work: Semi-stable Markov processes. I
cites work: Ray shooting on triangles in 3-space
cites work: Q4865431
cites work: Q3358267
description: scientific article; zbMATH DE number 1220840