Given a set $\cal D$ of unit disks in the plane and a set $C$ of colors. Every disk in $\cal D$ is colored with one of the colors in $C$. Note that multiple disks may be colored with the same color. Every color $c_i \in C$ is associated with a weight $w_i$.

for every path $p$ in the plane, we define the weight of $p$ as the sum of the weights of the colors that at least one of the circles with that color is crossed by $p$.

In addition, two points $s$ and $t$ is given in the plane and the goal is to find a path between $s$ and $t$ with the minimum total weight. What is the best approximation factor we can guarantee?

  • $\begingroup$ What did you try? Where did you get stuck? $\endgroup$ – David Richerby Dec 11 '16 at 10:39
  • $\begingroup$ Currently, we know that the problem is $NP$-hard and admits no approximation better than $\log n$ where $n$ is the number of unit diks. $\endgroup$ – Z M Dec 11 '16 at 13:33

For a constant number of colors, the problem can be solved by considering all possible subsets of colors. The rest can be solved using a shortest path with memoization.

You can reduce set cover to this problem: Build a grid with $m+2$ rows and $n+2$ columns. Also assume all points in one column are connected, but connect the points in rows based on the following rule:

Each column represents a member of the universal set and each row a set. The boundary is a color with weight zero. Let $s$ be the leftmost uppermost point and $t$ be the rightmost and lowest point and remove the other two corners of the grid. Color the point $i,j$ with color $i$ if set $S_i$ contains $u_j$ and remove it otherwise. The minimum weight path in this graph is the same as the minimum set cover.

This subset of a grid, is a unit disk graph: allow the columns to be $cn$ apart from each other, where $c$ is the vertical distance between the first row and last row. So $\theta(\log n)$ is tight.

  • $\begingroup$ Thanks. Your construction reveals the negative side: no approximation better than $\log(n)$ is possible. Do you think any approximation factor can be guaranteed in polynomial time? $\endgroup$ – Z M Dec 12 '16 at 7:06
  • $\begingroup$ You can convert every unit disk graph into a grid: $\endgroup$ – Sepid Dec 12 '16 at 14:53
  • $\begingroup$ en.wikipedia.org/wiki/Unit_disk_graph#Computational_complexity $\endgroup$ – Sepid Dec 12 '16 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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