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
All of whose edges are parallel to the $x$- or $y$-axes, and all of whose vertices are lattice points.
Which makes only left (counterclockwise) turns, when directed.
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:
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:
But in general, especially with many horizontal and vertical collinearities among the points of $S$, there are options, some shorter than others. E.g.:
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: