New Results in Sona Drawing: Hardness and TSP Separation

We construct a problem instance whose minimum-length TSP tour is longer than its minimum-length sona drawing by a factor within $\varepsilon$ of $\frac{14+8\sqrt{2}+\pi(\sqrt{2}+1)}{8+4\sqrt{2}+\pi(\sqrt{2}+1)}$. Our construction is illustrated in Figure 1 and follows a fractal approach with $\varepsilon^{-1}$ levels (for simplicity, we assume that $\varepsilon^{-1}$ is an integer).

1. 1.

   We start by defining a few auxiliary points:

   1. (a)

      The initial set of auxiliary points $A_{0}$ is the intersection between a slightly shifted integer lattice and the $L_{1}$ ball $B(0,\varepsilon^{-1})$ of radius $\varepsilon^{-1}$ centered at the origin. That is, $A_{0}=\left\{(\frac{2i+1}{2},\frac{2j+1}{2})\mathrel{:}i,j\in\mathbb{Z}\right\}\cap\left\{(x,y)\mathrel{:}|x|+|y|\leq\varepsilon^{-1}\right\}$. In Figure 1(a), the auxiliary points are exactly the intersections of solid red lines.

   2. (b)

      Then, in Step $i$ (starting with $i=1$), for each auxiliary point $p\in A_{i-1}$, we add five points to $A_{i}$: $p$ itself, and four new points at distance $\left(\frac{1}{1+\sqrt{2}}\right)^{2i}$ from $p$ in each of the four cardinal directions. Let $A=A_{\varepsilon^{-1}}$. By construction, we have $|A_{i}|=5^{i}|A_{0}|$ and $|A_{0}|=2\varepsilon^{-2}+O(\varepsilon^{-1})$. We note that set $A$ contains auxiliary points (not sites). These points will not be part of the instance.

2. 2.

   We now use the auxiliary points to create some sites (the isolated black points of Figure 1):

   1. (a)

      For any $i\geq 1$ we define set $P_{i}$ of sites as follows: for each auxiliary point $q\in A_{i-1}$ we add the four sites whose $x$ and $y$ coordinates each differ from $q$ by $\frac{1}{2}\left(\frac{1}{1+\sqrt{2}}\right)^{2i}$. We note that all the added sites are distinct sites.

   2. (b)

      We define $P_{0}$ as the set of integer lattice points in $B(0,\varepsilon^{-1})$. Equivalently, for each auxiliary point $q\in A_{0}$ we add the sites whose $x$ and $y$ coordinates each differ from $q$ by $\frac{1}{2}$, but we do not add sites that lie outside $B(0,\varepsilon^{-1})$, which affects $O(\varepsilon^{-1})$ sites (out of $\Omega(\varepsilon^{-2})$ sites of $P_{0}$).

      In this case, the sites created by different auxiliary points may lie in the same spot. In total, $P_{0}$ contains only one site per auxiliary point of $A_{0}$ (except for $O(\varepsilon^{-1})$ auxiliary points near the boundary). Thus, $|P_{i}|=4\cdot|A_{i-1}|=4\cdot 5^{i-1}\cdot|A_{0}|$ (for $i\geq 1$) and $|P_{0}|=|A_{0}|+O(\varepsilon^{-1})=(2\varepsilon^{-2}+O(\varepsilon^{-1}))$.

   Let $P^{(1)}=P_{0}\cup P_{1}\cup\cdots\cup P_{\varepsilon^{-1}}$.

3. 3.

   Next, we place additional sona sites packing line segments and/or curves. Whenever we pack any curve, we place sites spaced at a distance $\delta$ small enough that the length of the shortest path that passes within $\delta$ of all of them is within a factor $(1-\varepsilon)$ of the length of the curve.

   1. (a)

      Solid lines as drawn in red in Figure 1(a): for each $x\in\{i+\frac{1}{2}\mathrel{:}-(\varepsilon^{-1}+1)\leq i\leq\varepsilon^{-1}\mbox{ and }i\in\mathbb{Z}\}$, we pack the vertical line segment with endpoints $(x,\varepsilon^{-1}+1-|x|)$ and $(x,|x|-\varepsilon^{-1}-1)$, and analogously with $y$ for the horizontal line segments.

   2. (b)

      In Step $i$ of the above recursive definition (starting with $i=1$), when we create four new auxiliary points of $A_{i}$ from a point $p\in A_{i-1}$, we also pack the boundary of the region within Euclidean distance $\frac{1}{2}\left(\frac{1}{1+\sqrt{2}}\right)^{2i}$ of the square whose vertices are the four auxiliary points of $A_{i}$. Note that this boundary region forms a square with rounded corners as in Figure 1(b). With these extra points we preserve the invariant that the auxiliary points are exactly the intersections of packed curves.

Let $P^{(2)}$ be the set of sites created in Step 3 in our construction, and $P=P^{(1)}\cup P^{(2)}$. This is a complete description of the construction.

We now find the minimum-length sona drawing of $P$. Each pair of consecutive points in a packed curve must be in a separate sona region, so any sona drawing must pass between them; in particular, any sona drawing must pass within $\delta$ of each of them, and so the length of any valid sona drawing is at least $1-\varepsilon$ times the length of the packed curves. Also, there’s a valid sona drawing that’s at most $1+\varepsilon$ times the length of the packed curves: follow all the packed curves exactly, adding small loops around the sona sites of the packed curves as necessary (loops small enough to lengthen the curve by a factor of at most $1+\varepsilon$). The graph of packed curves is Eulerian (because it’s defined as a union of boundaries of regions, which are cycles), so the TSP tour can follow an Eulerian circuit through it. At an intersection of packed curves, we have two options for the sona drawing (as shown in the inset images of Figure 1). We can have one sona path cross over the other in the Eulerian circuit (by including every site of the packed curve in a small loop). Alternatively, we can have one sona path cross over the other in two places $p$ and $q$ at the intersection, and leaving one sona site of the packed curve out of a small loop to be the sona site of the extra region between $p$ and $q$. In either case, we conclude that there is a valid sona path that follows an Eulerian circuit of the packed curves within $(1+\varepsilon)$. Note that, although our description focused in the sites of $P^{(2)}$, this is a valid sona tour for $P$ since the sites of $P^{(1)}$ lie in different faces.

The total length of the packed curves is hence a $(1+\varepsilon)$-approximation of the total length of the minimum-length sona drawing.

The total length of the packed segments of $P^{(2)}$ (the square lattice) is $4\varepsilon^{-2}+O(\varepsilon^{-1})$, since the area of the region $|x|+|y|<\varepsilon^{-1}$ and the number of lattice points in it are each $2\varepsilon^{-2}+O(\varepsilon^{-1})$.

Now we bound the length of the packed curves (rounded squares). In Step $i$ of the construction (starting with $i=1$), we added a packed curve that is the boundary of the region within Euclidean distance $\frac{1}{2}\left(\frac{1}{1+\sqrt{2}}\right)^{2i}$ of a square of side length $\left(\frac{1}{1+\sqrt{2}}\right)^{2i}$ (with a total length of $(4+\pi)\left(\frac{1}{1+\sqrt{2}}\right)^{2i}$).

Recall that we added one such curve for each of the points of $A_{i-1}$ and that $|A_{i}|=5^{i-1}(2\varepsilon^{-2}+O(\varepsilon^{-1}))$. Thus, the total length of the sona drawings introduced at Step $i$ is $(4+\pi)\left(\frac{1}{1+\sqrt{2}}\right)^{2i}5^{i-1}(2\varepsilon^{-2}+O(\varepsilon^{-1}))$.

For $\varepsilon$ small, this series is well-approximated by an infinite geometric series with sum $(2\varepsilon^{-2}+O(\varepsilon^{-1}))\left(\frac{4+\pi}{(1+\sqrt{2})^{2}\cdot\left(1-\frac{5}{(1+\sqrt{2})^{2}}\right)}\right)=(2\varepsilon^{-2}+O(\varepsilon^{-1}))\left(\frac{4+\pi}{2\sqrt{2}-2}\right)$, and adding in the length of the packed segments of $P^{(2)}$ (the square lattice) gives $(2\varepsilon^{-2}+O(\varepsilon^{-1}))\left(2+\frac{4+\pi}{2\sqrt{2}-2}\right).$

We have approximated the minimum length of a valid sona drawing; now we approximate the minimum length of a TSP tour.

Any TSP tour must also come within $\delta$ of every point on every packed curve, which requires a length at least $(2\varepsilon^{-2}+O(\varepsilon^{-1}))\left(2+\frac{4+\pi}{2\sqrt{2}-2}\right)$ as above. Also, the TSP tour must visit each site of $P^{(1)}$. We observe some properties of this set:

• •

  Set $P^{(1)}$ is defined so that sites are far from each other. Specifically, the Euclidean ball centered at any site $p\in P_{i}$ of radius $r_{i}=\frac{1}{2}\left(\frac{1}{1+\sqrt{2}}\right)^{2i}$ does not contain other sona sites. This means that we must include at least $2r_{i}$ in the length of the TSP tour for each point in $P_{i}$, for the part of the tour that passes from the boundary of this ball to $P_{i}$ and then back to the boundary.

• •

  There are $4\cdot 5^{i-1}(2\varepsilon^{-2}+O(\varepsilon^{-1}))$ sites in $P_{i}$ (for $i\geq 1$) and $(2\varepsilon^{-2}+O(\varepsilon^{-1}))$ sites in $P_{0}$.

When $\varepsilon$ tends to zero, the additional length needed in the TSP tour is

So, the total length of the TSP tour is at least $(2\varepsilon^{-2}+O(\varepsilon^{-1}))\left(2+\frac{4+\pi}{2\sqrt{2}-2}+2\sqrt{2}+3\right)$. Hence the ratio of the length of the TSP tour to the length of the sona drawing is, ignoring lower-order terms, $\frac{2+\frac{4+\pi}{2\sqrt{2}-2}+2\sqrt{2}+3}{2+\frac{4+\pi}{2\sqrt{2}-2}}=\frac{14+\pi(\sqrt{2}+1)+8\sqrt{2}}{8+4\sqrt{2}+\pi(\sqrt{2}+1)}\approx 1.54878753$.

Let $V$ be the set of $n$ vertices in a hard instance for finding a Hamiltonian cycle in grid graphs. We may form a hard instance of the minimum-length sona drawing problem for $L_{1}$ or $L_{2}$ distances by replacing each vertex in $V$ by a pair of sites, one at the original vertex position and the other at distance less than $\varepsilon$ from it, where $\varepsilon=\Theta(1/n)$ is chosen to be small enough that $4n\varepsilon<\sqrt{2}-1$. We set $L=n+2n\varepsilon$. For $L_{\infty}$ distance, we use a hard instance for $L_{1}$ distance, rotated by $45^{\circ}$.

If $V$ is a yes-instance for Hamiltonian cycle, let $C$ be a Hamiltonian cycle of length $n$ for $V$. We may form a sona drawing of length less than $L$ by modifying $C$ within a neighborhood of each pair of sites so that, for all but one of these pairs, it makes two loops, one surrounding each site (Figure 8), and so that for the remaining pair it makes one loop around one of the two sites and surrounds the other point by the face formed by $C$ itself. In this way, each face of the modified curve surrounds a single site of our instance. Each of these local modifications to $C$ may be performed using additional length less than $2\varepsilon$, so the total length of the resulting sona drawing is less than $L$.

If $V$ is a no instance for Hamiltonian cycle, let $C$ be any sona drawing for the resulting instance of the minimum-length sona drawing problem. Then $C$ must pass between each pair of sites in the instance, and by making a local modification of length at most $2\varepsilon$ near each pair, we can cause it to touch the point in the pair that belongs to $V$ itself. Thus, we have a curve of length $|C|+2n\varepsilon$ touching all points of $V$. Because $V$ is a no instance, the length of this curve must be at least $n+\sqrt{2}-1$, from which it follows that the length of $C$ is at least $n+\sqrt{2}-1-2n\varepsilon\geq L$.