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.

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₂ 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₂| + |V_≥3|, the total number of faces (including the outer face) is |T|+1, and the total number of edges is ½(3|V₂| + D_≥3). Euler's formula now gives us |V₂| + |V_≥3| + |T| + 1 = ½(3|V₂| + D_≥3) + 2, which we can rewrite as D_≥3 = 2|V_≥3| + |T| + (|T| - 2 - |V₂|). 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?

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 Jordan 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: 4r² = ||τ(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))² = 2r² + 2x² + τ_y(f(x))² + h(x)² + τ_y(g(x))². We rewrite this to: τ_y(f(x))² + h(x)² + τ_y(g(x))² ≤ 2r² − 2x². 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)² ≤ 2r² − 2x², and h(x) ≤ (2/√3)√(r² − x²). Note that ∫_−r^rh(x)dx gives us an upper bound on the two-dimensional measure of the points in the curve section under consideration. We have ∫_−r^rh(x)dx ≤ (1/√3)∫_−r^r2√(r² − x²)dx = (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² / (¹⁄₆π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?

Propose (write or find) lyrics for the Hilbert song. Here is the melody, a sonification of the fourth level of refinement of the Hilbert curve:

For further explanation, see my page on the sound of space-filling curves.

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?

Suppose we have k functions f₁,…,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₁,…,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 2k points that consists of the immediate predecessors and successors of p in S₁,…,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⁻¹ 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.¹⁾)

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₁,…,f_d such that φ can be bounded? Or can we prove that φ cannot be bounded if k=d?

(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?

(updated 25 September 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).

The problem is, in general, NP-hard for non-planar graphs, and can be solved in polynomial time for trees:

• Shortest-Path-Preserving Rounding.
  By Herman Haverkort, David Kübel, and Elmar Langetepe.
  Computing Research Repository (arXiv.org), 1905.08621, 2019.
  text

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.