Complexity Bounds for Ray Tracing and Illumination in 2D Using Spy Mirrors

EasyChair Preprint 12070, version 2

Abstract

Since the seminal work of Reif et al. from 1994, it is known that Ray Tracing in three dimensions is as hard as solving the Halting problem. However, the question of whether this result also holds for two dimensions remains open. In this paper, we address this problem and demonstrate that for two dimensions, Ray Tracing is NP-complete when the number of reflections is linearly bounded, and when linear one-way mirrors and mirrors are allowed.

To achieve this, we examine various sub-classes of one-way mirrors. Our hardness result holds when we allow natural one-way mirrors that are half-transparent from both sides or when we permit only merging and splitting one-way mirrors. Merging mirrors possess one side that is totally reflective and another side that is perfectly transparent, while split mirrors have one side that is half-transparent and the other side that is fully transparent.

In the absence of half-mirrors, we establish a polynomial time bounded algorithm for polynomial reflections in any k-dimensional space, provided the mirrors are represented as k-simplexes with rational coordinates. When given merging mirrors and mirrors represented as line segments or parabolic shapes, we show that Ray Tracing becomes P-hard in two dimensions.

Moreover, we present the first computational complexity results for the Illumination problem. Given a light source, we inquire whether a specific point is illuminated. We prove that this problem is NP-hard for two dimensions, considering mirrors represented as line segments. On the other hand, for the upper bound, we demonstrate that Illumination in k-dimensions, with mirrors represented as k-simplexes with rational point coordinates and linearly bounded reflections, can be solved in NP.

Keyphrases: computational complexity, illumination, ray tracing

@booklet{EasyChair:12070,
  author    = {Rosemary Adejoh and Andreas Jakoby and Sneha Mohanty and Christian Schindelhauer},
  title     = {Complexity Bounds for Ray Tracing and Illumination in 2D Using Spy Mirrors},
  howpublished = {EasyChair Preprint 12070},
  year      = {EasyChair, 2024}}