# Unsolved puzzles

On this page I collect a selection of the combinatorial and/or algorithmic puzzles that, so far, remained unsolved in my publications. Please do not hesitate to contact me if you have any solutions or insights on these puzzles.

## Separating groups of points using disjoint disks

Prove the NP-hardness or give an efficient algorithm for the following problem: given a set of points in the plane, subdivided into groups, decide whether there is a set of disjoint disks that each contain exactly one group of points, such that each group lies in the interior of exactly one disk.

**Why?** This is a simplified version of a problem arising in the construction of *blob collection maps* as proposed in the following manuscript:

**Embedding cues about travel time in schematic maps.**
By Herman Haverkort.

Presented at the

*Schematic Mapping Workshop 2014*.

text (draft of full report).

Consider a set *S* of geometric objects, each of which is topologically equivalent to a ball *but not necessarily convex*, with the following property: any object *U* that is similar to an element of *S*, can be tiled with a set *T* of tiles such that each tile of *T* has diameter at most 1 and is similar to an element of *S*. Given such a tiling and any point *p*, let d(*p*) be the number of tiles whose closures contain *p*. Let *V*_{≥k} be the set of points *p* such that d(*p*) ≥ *k* and d(*p*) > d(*q*) for any point *q* that is infinitesimally close to *p*. So *V*_{≥4} is essentially the vertices of the tiling, except for those on the boundary of *U* that are incident on only three tiles. Let *D*_{≥k} be the sum of d(*p*) over all points *p* in *V*_{≥k}. Can we prove that, for any fixed set *S* and any corresponding object *U* that is large enough, we must have *D*_{≥4} > 3|*V*_{≥4}| +
*|T|*? Or in words, modulo the boundary effects: can we prove that the total number of vertex-tile incidences must exceed the number of tiles plus three times the number of vertices?

**Why?** Proving the claim would rule out the existence of “at-least-somewhat-well-behaved” three-dimensional space-filling curves with Arrwwid number 3, a property that may be relevant to applications in data structures. For details, see:

**Recursive tilings and space-filling curves with little fragmentation.**
By Herman Haverkort.

*Journal of
Computational Geometry*, 2(1):92–127, 2011.

text

**What does Euler have to do with it?** For two-dimensional subdivisions, the claim to prove was: *D*_{≥3} > 2|*V*_{≥3}| + |*T*|. Let *V*_{2} be the set of vertices on the boundary that are incident on only two tiles and the outer face. Thus, the total number of vertices is |*V*_{2}| + |*V*_{≥3}|, the total number of faces (including the outer face) is |*T*|+1, and the total number of
edges is ½(3|*V*_{2}| + *D*_{≥3}). Euler's formula now gives us |*V*_{2}| + |*V*_{≥3}| + |T| + 1 = ½(3|*V*_{2}| + *D*_{≥3}) + 2, which we can rewrite as
*D*_{≥3} = 2|*V*_{≥3}| + |*T*| + (|*T*| - 2 - |*V*_{2}|). Because, with increasing size of *U*, the number of tiles grows faster than the number of vertices on the boundary, this proves *D*_{≥3} > 2|*V*_{≥3}| + *|T|* for large enough *U*. Can we come up with some kind of
“Euler formula” to derive a similar conclusion, namely *D*_{≥4} > 3|*V*_{≥4}| +
*|T|*, in three dimensions?

## A lower bound on the dilation of plane-filling curves

Let τ: [0,1] → *T* be a continuous surjection to a compact set *T* in the plane such that for any *a* ≤ *b* ∈ [0,1], the union of τ(*t*) over all *t* ∈ [*a*,*b*] has two-dimensional Lebesgue measure *b*−*a*.
In other words, τ is a measure-preserving plane-filling curve. The dilation of the curve is the maximum, over all *a* < *b* ∈ [0,1], of ||τ(*a*)τ(*b*)||² / (*b*−*a*), where ||τ(*a*)τ(*b*)|| is the Euclidean distance between τ(*a*) and τ(*b*). Prove a tight lower bound on the smallest possible dilation for any measure-preserving plane-filling curve.

**Why?** The locality-preserving properties of plane-filling curves are often what makes them useful in applications, and dilation is one of the most-studied metrics of locality-preserving properties.

**What is known?** The square-filling Sierpiński curve, which can be described as the concatenation of two Pólya curves that fill an isosceles right triangle, has dilation 4. I tend to suspect that this is optimal, because whenever I come up with a (tentative) lower bound construction for a dilation lower than 4 and I try to match that lower bound, I end up reinventing the Pólya curve (or something worse). But that is no proof. We *can* actually prove a matching lower bound for curves that fill the plane triangle by triangle, or rectangle by rectangle in a regular grid pattern. For details, see:

**Locality and bounding-box quality of two-dimensional space-filling curves.**
By Herman Haverkort and Freek van Walderveen.

*Computational Geometry*, 43(2):131–147, 2010.

text

A more general lower bound, but probably far from tight, can be proven as follows. Let δ be the dilation of
a curve, and consider a pair (*a*,*b*) that determines the dilation, that is, δ = ||τ(*a*)τ(*b*)||²
/ (*b*−*a*). Orient the coordinate system such that τ(*a*) = (−*r*,0) and τ(*b*) = (*r*,0),
for some *r*. For any *t*, let τ_{x}(*t*) and τ_{y}(*t*) be the coordinates of τ(*t*).
For any *x* ∈ [−*r*,*r*], let *f*(*x*) be the value of *t* that *minimizes* τ_{y}(*t*)
subject to *t* ∈ [*a*,*b*] and τ_{x}(*t*) = *x*, and let
*g*(*x*) be the value of *t* that *maximizes* τ_{y}(*t*)
subject to *t* ∈ [*a*,*b*] and τ_{x}(*t*) = *x*. Assume *f*(*x*) ≤ *g*(*x*) (the calculations for the opposite case are similar). Let *h*(*x*) be τ_{y}(*g*(*x*))−τ_{y}(*f*(*x*)). Note that *h*(*x*) is an upper bound on the one-dimensional measure of the points with the given *x*-coordinate
in the curve section under consideration.
By the definition of the dilation δ, we have, for any *x*:
4*r*²
= ||τ(*a*)τ(*b*)||²
= (*b*-*a*)·δ
= (*f*(*x*)−*a*)·δ + (*g*(*x*)−*f*(*x*))·δ + (*b*−*g*(*x*))·δ
≥ ||τ(*a*)τ(*f*(*x*))||² + ||τ(*f*(*x*))τ(*g*(*x*))||² + ||τ(*g*(*x*))τ(*b*)||²
= (*r*+*x*)² + τ_{y}(*f*(*x*))² + *h*(*x*)² + (*r*−*x*)² + τ_{y}(*g*(*x*))²
= 2*r*² + 2*x*² + τ_{y}(*f*(*x*))² + *h*(*x*)² + τ_{y}(*g*(*x*))².
We rewrite this to:
τ_{y}(*f*(*x*))² + *h*(*x*)² + τ_{y}(*g*(*x*))² ≤ 2*r*² − 2*x*².
Given *r* and *x*, we maximize *h*(*x*) if τ_{y}(*f*(*x*)) = −½*h*(*x*) and,
therefore, τ_{y}(*g*(*x*)) = ½*h*(*x*), so we have:
(3/2)*h*(*x*)² ≤ 2*r*² − 2*x*², and
*h*(*x*) ≤ (2/√3)√(*r*² − *x*²).
Note that ∫_{−r}^{r}*h*(*x*)d*x* gives us an upper bound on the two-dimensional measure of the points in the curve section under consideration. We have
∫_{−r}^{r}*h*(*x*)d*x* ≤
(1/√3)∫_{−r}^{r}2√(*r*² − *x*²)d*x* =
(1/√3)π*r*² (that is, the area of an ellipse obtained by squeezing the circle with diameter τ(*a*)τ(*b*) by a factor √3).
Therefore, *b*−*a* ≤ (1/√3)π*r*² and δ = ||τ(*a*)τ(*b*)||²/(*b*−*a*) ≥ 4√3/π ≈ 2.21.

Note that the lower bound could only be realized if the curve section from τ(*a*) to τ(*b*) fills exactly said ellipse, *and* fills smaller ellipses of the same shape on the way from τ(*a*) to τ(*f*(*x*)), from τ(*f*(*x*)) to τ(*g*(*x*)), and from τ(*g*(*x*)) to τ(*b*). However, that is not possible, since the last three ellipses do not tile the first. Indeed, it seems that a Pólya curve might be the best realizable approximation of this construction, but can we prove this?

Another general lower bound can probably be proven as follows. Any plane-filling curve has points in the
interior of *T* that are visited by the curve three times. Consider a disk of radius *r* centred on such a
point *p*, such that the disk lies entirely within *T*, and the curve enters the disk, visits *p*, and
leaves the disk at least three times. Thus there are at least six pieces of the curve that lie entirely inside
the disk and have one end on the boundary of the disk and one end in the centre. The smallest of these pieces
fills at most one sixth of the disk, and therefore has dilation at least *r²* /
(^{1}⁄_{6}π*r²*) ≈ 1.91. This is not better than the bound mentioned above, but maybe the
ideas behind these bounds can be combined to make a better bound.

So the question is: can you prove a lower bound that is substantially better than 4√3/π ≈ 2.21 (say, at
least 7/3), or can you construct a measure-preserving plane-filling curve with dilation less than 4?

## Lyrics for a space-filling curve

## Non-trivial reptilings of triangles

Which triangles admit a tiling that consists of mutually congruent smaller copies of the original triangle, but not in a regular grid pattern? We know the answer for several classes of triangles, but the problem is still open for triangles with angles π / *m*, *k*π / *m* and (*m*−*k*−1)π / *m*, for integer *k* ≥ 2 and *m*, where *m* / 3 ≤ *k*+1 < *m* / 2 and such that no two sides of the triangle have a rational length ratio, but there are non-zero natural numbers λ, µ, ν such that λ sin(π / *m*) = µ sin(*k*π / *m*) + ν sin( (*k* + 1)π / *m*). Do such triangles actually exist? For background information on this question, see:

**Reptilings and space-filling curves for acute triangles.**
By Marinus Gottschau, Herman Haverkort, and Kilian Matzke.

*Discrete and Computational Geometry*, in press, available online 2017.

edited text from publisher; text from
arXiv.org

A related puzzle from the same paper is the following: is there an oblique triangle that can be tiled with *less* than 169 mutually congruent smaller copies of itself, such that two tiles meet in a vertex of the complete triangle?

## Nearest-neighbour-preserving space-filling curves

Suppose we have *k* functions *f*_{1},…,*f*_{k} from [0,1]^{d} to [0,1] that have some favourable properties, which I will explain shortly. Now, given any set of *n* distinct points *S*⊂[0,1]^{d}, we can construct *k* ordered lists *S*_{1},…,*S*_{k}, such that *S*_{i} contains the points of *S* in order of increasing image under *f*_{i}. For any point *p* in *S*, let *N(S,p)* be the set of at most 2*k* points that consists of the immediate predecessors and successors of *p* in *S*_{1},…,*S*_{k}. The favourable property that we are looking for is this: there is a constant φ (which may depend on *d*), such that, regardless of the choice of *S* and *p*, the L_{∞}-distance between *p* and the nearest point in *N(S,p)* is at most φ times the L_{∞}-distance between *p* and the nearest point in *S*\{*p*}. What are the best bounds on *k* and φ, as a function of *d*, that can we realize?

**What is known?** For even *d*, if we choose *k*=*d*+1 and each *f*_{i} such that its inverse *f*_{i}^{−1} is, for example, a *d*-dimensional Hilbert curve or Z-order traversal of the cube [−1+i/(*d*+1),1+i/(*d*+1)]^{d}, then we get approximation ratio φ≤2(*d*+1) (Liao et al.^{1)})

The first questions: Can we prove that φ must be Ω(*d*) if *k*=*d*+1? Given any fixed (even) *d* and *k*=*d*, is there a set of functions *f*_{1},…,*f*_{d} such that φ can be bounded? Or can we prove that φ cannot be bounded if *k*=*d*?

## The depth of enclaves in random black/white grids

(The Baarle nested enclaves problem) Suppose we have a grid of *n* hexagonal (or square) cells in a regular honeycomb (or square grid) pattern, with a roughly hexagonal (or square) outer border, and we colour each cell, independently, white with probability 1/2; if we do not colour it white, we colour it black. Let the *depth* of a cell in the resulting coloured grid be the minimum number of times we have to cross a white/black or black/white border to walk from that cell to the boundary of the grid without going through vertices. Let the depth of a coloured grid be the depth of the deepest cell in the grid. Based on some experiments, I dare to make the following conjecture: the expected depth of the hexagonal grid is Θ(log *n*), whereas the expected depth of the square grid is Θ(*n*^{α}) for some constant α ≈ 0.4. Can you prove this?

## Shortest-path-preserving rounding of weights in a graph

(updated 17 January 2019) Prove the NP-hardness or give an efficient algorithm for the following problem: given a weighted undirected planar graph *G* with non-negative weights, in which each edge is a shortest path, decide whether one can construct a copy *G'* of *G* in which all weights are replaced by integers, such that the following conditions hold:

the difference in weight between any shortest path in *G* and the corresponding path in *G'* is less than 1;

any shortest path in *G* is a shortest path in *G'*.

(optional) any shortest path in *G'* is a shortest path in *G*.

**Why?** This is a simplified version of a problem arising in the construction of *blob collection maps* as proposed in the following manuscript:

**Embedding cues about travel time in schematic maps.**
By Herman Haverkort.

Presented at the

*Schematic Mapping Workshop 2014*.

text (draft of full report).

We believe we have found a proof that the problem is, in general, NP-hard for non-planar graphs, and we believe we have found a polynomial-time algorithm that solves the problem for trees—we are currently writing up these results. However, from an application point of view, the case of planar graphs may be more relevant, and for planar graphs we still do not know.