8
$\begingroup$

Suppose one has $n$ perfect two-sided mirror segments in the plane $\mathbb{R}^2$. The segments are open, excluding their endpoints. They are disjoint as closed segments, i.e., no pair shares an endpoint.

Q. Given two points $s$ and $t$, what is the computational complexity of deciding whether or not it is possible to shoot a ray from $s$ and hit $t$ by reflection from the mirrors?


          ReflectionComplexity
All segments endpoints, and $s$ & $t$, have integer coordinates in $[0,N]$, $N=2^L$. So all coordinates can be represented with $L$ bits.

I've thought about such reflections, but not in terms of computational complexity. And I do not recall this question being addressed in the literature. But perhaps it it is implied by more general results...?

$\endgroup$
6
  • 5
    $\begingroup$ Isn't a question like this considered in ray tracing algorithms? $\endgroup$ Commented Feb 21, 2015 at 3:08
  • 2
    $\begingroup$ @TheMaskedAvenger: Maybe not exactly -- in a typical ray tracing application, $s$ would be given, and the algorithm needs to find all points $t$ for which there is a ray from $s$ to $t$. The given question asks for the complexity of deciding whether a given single point $t$ can be reached by a ray starting at $s$. $\endgroup$
    – Stefan Kohl
    Commented Feb 21, 2015 at 10:16
  • $\begingroup$ I have a (very!) vague sense that it might be possible to construct ("rig") an NP-hardness proof... I am currently thinking of reduction from Set Partition. $\endgroup$ Commented Feb 21, 2015 at 22:48
  • 1
    $\begingroup$ Vaguely related question: mathoverflow.net/questions/34326/polygonal-billards-programs $\endgroup$
    – user25199
    Commented Feb 23, 2015 at 16:14
  • 2
    $\begingroup$ My intuition tells me that this problem is at least NP-hard and you can probably use a fairly standardized 'gadget' construction to build an appropriate SAT instance (similar to the gadgets for games like Minesweeper etc). $\endgroup$ Commented Jul 9, 2015 at 22:00

0

You must log in to answer this question.