Title :
The computability and complexity of optical beam tracing
Author :
Reif, John H. ; Tygar, J.D. ; Yoshida, Akitoshi
Author_Institution :
Dept. of Comput. Sci., Duke Univ., Durham, NC, USA
Abstract :
The ray-tracing problem is considered for optical systems consisting of a set of refractive or reflective surfaces. It is assumed that the position and the tangent of the incident angle of the initial light ray are rational. The computability and complexity of the ray-tracing problems are investigated for various optical models. The results show that, depending on the optical model, ray tracing is sometimes undecidable, sometimes PSPACE-hard, and sometimes in PSPACE
Keywords :
computability; computational complexity; computational geometry; decidability; geometrical optics; light reflection; light refraction; physics computing; PSPACE-hard problem; complexity; computability; incident angle; optical beam tracing; optical models; ray-tracing problem; reflective surfaces; refractive surfaces; undecidable problem; Computer graphics; Contracts; Geometrical optics; Lenses; Mirrors; Optical beams; Optical computing; Optical design; Optical refraction; Ray tracing;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89529
