← All Problems
Open

Limited Reflection Ray Tracing (LRRT)

Category: Logic

Input

A set of $n$ flat mirrors of lengths $l_1, \ldots, l_n$, their placements at rational points in the plane, a source point $S$, the trajectory of a single beam emitted from $S$, and a designated mirror $M$.

Problem

Is $M$ hit by the beam emitted from $S$ within $n$ reflections? At the mirrors, the incidence angle of the beam equals the angle of reflection.

Status

Open (Greenlaw, Hoover, and Ruzzo [2]).

Remarks

The General Ray Tracing Problem is to determine if a mirror is ever hit by the beam. When the mirrors are points, that is have no length, the general problem is in $\NC$ [2]. In two or more dimensions, the general problem is in $\mathsf{PSPACE}$ (Reif, Tygar, and Yoshida [1]). In three dimensions, with mirrors placed at rational points, the general problem is $\mathsf{PSPACE}$-hard [1]. The general problem is open for all mirrors of a fixed size as well. See [1] for a detailed discussion.

References

  1. J. H. Reif, J. D. Tygar, and A. Yoshida (1990). The computability and complexity of optical beam tracing.
  2. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.6.1.