2
$\begingroup$

Problem definition

The world consists of an infinite three-dimensional cartesian grid, i.e. every position is in $P = \mathbb{Z}^3$.

Neighbours of a position $p \in P$ are defined by $N(p) = \{p + e_1, p - e_1, p + e_2, p - e_2, p + e_3, p - e_3\}$, where $e_i$ are the unit vectors, for example $e_1 = (1,0,0)^T$.

For a torch placement $T \subset P$, at each position $p$, there is a voxel $b(T, p)$, which is air, a torch or stone: $$ M \subset 2^{P} \\ b: M \times P \rightarrow \{air, torch, stone\} \\ b(T, p) = torch \iff p \in T $$ Furthermore, a torch can only exist next to stone and the positions of stone voxels are fixed: $$ \forall p \in P: \left(b(T, p) = torch \Rightarrow \exists n \in N(p): b(\{\}, n) = stone\right) \\ \forall p \in P: \left(b(T, p) = stone \iff b(\{\}, p) = stone \right) $$

Light originates from torches, recursively spreads to neighbouring positions, and does not go into stone. This means the light $l(T, p)$ at the position $p$ is defined by $$ l(T, p) = \begin{cases} 0, & b(T, p) = stone \\ 12, & b(T, p) = torch \\ max(\{1\} \cup \{l(T, n) | n \in N(p)\}) - 1, & b(T, p) = air \end{cases} $$

Light at $p$ has an effect on visibility ($v(p)$) if and only if it is next to stone and not in stone itself, i.e. $$ v(p) \iff b(\{\}, p) \neq stone \land \exists n \in N(p): b(\{\}, n) = stone $$

The optimisation problem is to find a torch placement $T$ such that everything is visible with a light of at least one and as few torches as possible are placed: $$ T_{opt} \in argmin_{T}\left\{|T| : \forall p \in P: (v(p) \Rightarrow l(T, p) > 0) \right\} $$

To make the optimisation feasible, we assume that everything outside a cube of side length $a$ is stone: $$ \forall p \in P: \forall i \in \{1,2,3\}: (p_i < 0 \lor p_i \geq a \Rightarrow b(\{\}, p) = stone) $$

My Question

I know that it is possible to find a $T$ with a greedy algorithm which places torches one after another until everything is lit up sufficiently, but it does not give an optimal solution in general, so it gives only an upper bound on $|T_{opt}|$.

Is there a computational and memory-efficient algorithm to find a $T_{opt}$ and what is its asymptotic time and memory requirement with respect to $a$?

$\endgroup$
2
  • $\begingroup$ Your problem formulation allows light to bend around corners. Is that intended/correct? $\endgroup$
    – D.W.
    Nov 8, 2023 at 20:17
  • $\begingroup$ @D.W. Yes, it is intended. Light going around corners may be considered a coarse approximation of global illumination. $\endgroup$ Nov 12, 2023 at 15:55

1 Answer 1

3
$\begingroup$

No, assuming $\mathsf{P} \neq \mathsf{NP}$ there is no efficient algorithm for optimal torch placement, even if the world is just a 2D grid.

This can be shown by providing a reduction from the vertex cover problem on cubic planar graphs, which is known to be $\mathsf{NP}$-hard. I'm only going to sketch the general idea of the reduction, so I'll be somewhat sloppy.

Let $G = (V, E)$ be a cubic planar graph with $n = |V|$ vertices edges and consider an embedding on the infinite grid such that all edges can be drawn with axis-parallel polylines between the corresponding vertices. Now "scale up" this embedding so that each vertex becomes a square and there is "enough space" between different edges and vertices.

The whole world (a plane) except for consists of stone except for the following "room" and "tunnel" gadgets, that will encode vertices and edges (respectively).

Each vertex $v$ of the graph is encoded by the following "room".

This room has three openings on the top which we will use to connect the three edges incident to $v$. Moreover, this room has the following properties:

  • Regardless of the placement of the torches outside of the room, there must be at least one torch inside the room.
  • Regardless of the placement of the torches outside of the room, there is exactly only way to illuminate the whole room with one torch, i.e., placing the torch in the spot highlighted in yellow.
  • A torch in the yellow spot "provides no light" to the locations immediately after the three openings (marked with $x$).
  • Any light coming from one of the three openings cannot "reach" any other opening.
  • Using two torches (e.g. in the yellow and in the red spot), it is possible to light the whole room and provide a light level of at least $4$ to all the locations marked with $\times$.

Each edge $e=(u,v)$ is encoded with a "tunnel of width 1" having a length of $23k_e + h_e$ where $k_e$ is a positive integer and $h_e \in \{1,2\}$. The tunnel can twist and bend in 90-degree turns and connects an opening of $u$ with an opening of $v$. Notice that it is always possible to create tunnels of the prescribed length. Indeed, it suffices to ensure that the tunnels detaching form a node continue straight for at least $30$ blocks. In this way each tunnel has at least $12$ sections as the one shown below in figure (a) (i.e., $6$ sections for each endvertex). Each of these $12$ sections can be kept unaltered or it can be replaced with the one of figure (b) to extend the length of the tunnel by $2$. This allows to extend the length by any even amount of choice ranging from $0$ to $24$, which is always enough to satisfy the constraint.

Consider any (partial) placement of torches that lights up all the rooms and let $23k_e + h_e$ be the length of a generic tunnel that corresponds to edge $e = (u,v)$. If $u$ and $v$ have exactly one torch each, at least $k_e+1$ torches need to be placed in the tunnel (since each torch lights up at most $23$ spots). If at least one of $u$ and $v$ provides a light level of at least $2$ on the first location of the tunnel (marked with $\times$), then $\left\lceil \frac{23k_e+h_e - 2}{23} \right\rceil \le k_e$ torches suffice. Moreover, regardless of the light levels provided by $u$ and $v$ on their respective entrances of the tunnel (which can be at most $11$), at least $\left\lceil\frac{23k_e+h_e - 2 \cdot 11}{23} \right\rceil \ge \left\lceil \frac{23k_e - 21}{23} \right\rceil = k_e$ torches are needed to light up the tunnel.

This shows that if there exists a vertex cover $S$ of size at most $x$, we can light up all the world with at most $n + x + \sum_{e \in E} k_e$ torches (place a torch in the yellow spot of each room, place a torch in the red spot of the rooms corresponding to vertices in $S$, use $k_e$ torches for each tunnel $e$).

On the other hand, if we can light up the whole world with some arrangement of at most $n + x + \sum_{e \in E} k_e$ torches, then there must also be an arrangement that uses at most the same number of torches in total but uses exactly $k_e$ torches for each tunnel $e$ (there cannot be less than $k_e$ torches in the tunnel; if there are more than $k_e$ torches then add one to an arbitrary endvertex of $e$ and re-light the tunnel using exactly $k_e$ torches).

Consider such an arrangement: since each tunnel $e=(u,v)$ uses exactly $k_e$ torches, at least one of the rooms of $u$ and $v$ contains more than one torch. Then the set $S$ of vertices whose rooms contain $2$ or more torches is a vertex cover. Since each room must use at least one torch, $|S| \le \left( n + x + \sum_{e \in E} k_e \right) - \sum_{e \in E} k_e - n = x$.

$\endgroup$
2
  • $\begingroup$ Thanks. I assume that it is possible to encode an arbitrary cubic planar graph with $\Omega(a)$ vertices on the grid if everything outside a square of side length $a$ is stone. $\endgroup$ Nov 12, 2023 at 15:51
  • $\begingroup$ Yes, an orthogonal embedding of a planar graph (with maximum degree at most $4$) can be found in linear time see e.g., this paper. $\endgroup$
    – Steven
    Nov 12, 2023 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.