3
$\begingroup$

Let $S$ be a finite set of lattice points in $\mathbb{Z}^2$. My question is, roughly:

Q. How can a shortest lattice spiral that passes through every point of $S$ be found?

A lattice spiral (my terminology) is a simple (non-self-intersecting) open curve

  1. All of whose edges are parallel to the $x$- or $y$-axes, and all of whose vertices are lattice points.

  2. Which makes only left (counterclockwise) turns, when directed.

  3. Is not a "double spiral" in the sense that, if the edges lying on the axis-parallel bounding box are removed, the remaining edges form a connected curve.

This 3rd condition may seem unnatural—and I am not certain I've captured it correctly—but is intended to exclude the right figure below:


      SpiralNot
I believe I have proved that, for any $S$, there exists a lattice spiral covering $S$, i.e., every point of $S$ lies on the spiral. The proof relies on nested bounding boxes: The bounding box of $S$ includes some points $S_0$. Then the bounding box of $S \setminus S_0$ includes points $S_1$. Continuing in this manner leads to nested bounding boxes. Then spirals can be connected from the innermost box outward.

Sometimes, a given $S$ leaves very little choice:


      SpiralDiagonal
But in general, especially with many horizontal and vertical collinearities among the points of $S$, there are options, some shorter than others. E.g.:
      SpiralEx2
My question is: Is there an efficient algorithm that will find a shortest spiral for a given $S$, where "shortest" is defined by the Euclidean length of the edges of the spiral? Are there properties of such a shortest spiral that could help avoid a brute-force search? (Another variant is to define length as the number of edges, ignoring their Euclidean length. The spiral right above is shorter in both senses.)

My question is inspired by (and hopefully easier than) some apparently difficult questions posed by Filip Morić, discussed in this recent paper:

Dumitrescu, Gerbner, Keszegh, Tóth. "Covering paths for planar point sets." Discrete & Computational Geometry, Vol.51, No.2, Mar.2014, 462--484.


(Added in response to a question). Not quite what I intended, but this is a spiral according to my definition:
  SpecialSpiral

$\endgroup$
1
$\begingroup$

Given the handedness of the spiral and the direction of the spiral when hitting the last point, there is a unique spiral that passes through all the points. Enumerating the 8 possibilities yields the answer.

Proof:

Assume without loss of generality that the spiral turns clockwise and ends facing south. Clearly, the spiral ends on a point in $p = (x, y) \in S$. No point can lie strictly to the east of $p$, and among points sharing the same ordinate, $p$ must be the southernmost. Thus, $p$ is determined uniquely.

If we remove $p$ from $S$, we can now determine the last point the spiral hit when it was headed east, prior to turning south. It is the northernmost, then easternmost point in the set.

Repeating the process, we exhaust all the points and determine the unique clockwise spiral that ends facing south.

The same process can be repeated for each direction, clockwise and counter clockwise and the length of the 8 spirals can be compared.

$\endgroup$
  • $\begingroup$ Why must $p$ be southermost? If there are several points sharing that same $x$-coordinate, it seems that all are candidates for the last point. $\endgroup$ – Joseph O'Rourke Sep 5 '14 at 12:21
  • $\begingroup$ I suppose your definition of a spiral does include this case. I was assuming that no two distinct parallel edges could be on the same line - the algorithm might be salvageable though. $\endgroup$ – Arthur B Sep 5 '14 at 12:24
  • $\begingroup$ Yes. Already, though, you've provided insights I didn't see. Thanks! $\endgroup$ – Joseph O'Rourke Sep 5 '14 at 12:26
  • $\begingroup$ In fact, I think this can only happen in the very last segment. So you might need to try different starting points, but not all of them will yield a feasible spiral $\endgroup$ – Arthur B Sep 5 '14 at 12:30
  • $\begingroup$ Wait actually, how can it be not the southernmost easternmost point if you apply condition 3? All the examples I can think of become disconnected if you remove the edges lying on the bounding box. $\endgroup$ – Arthur B Sep 5 '14 at 13:00

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.