User Tools

Site Tools


unsolved_puzzles

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.

Shortest-path-preserving rounding of weights in a graph

Prove the NP-hardness or give an efficient algorithm for the following problem: given a weighted undirected 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.

If it helps, assume the graph is planar or near-planar.

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).

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? Same application as the previous problem.

An Euler formula for tiles and vertices in three-dimensional subdivisions

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 Vk 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 Dk be the sum of d(p) over all points p in Vk. 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 V2 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 |V2| + |V≥3|, the total number of faces (including the outer face) is |T|+1, and the total number of edges is ½(3|V2| + D≥3). Euler's formula now gives us |V2| + |V≥3| + |T| + 1 = ½(3|V2| + D≥3) + 2, which we can rewrite as D≥3 = 2|V≥3| + |T| + (|T| - 2 - |V2|). 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 ab ∈ [0,1], the union of τ(t) over all t ∈ [a,b] has two-dimensional Lebesgue measure ba. 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)||² / (ba), 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)||² / (ba). 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 c(x) be the value of t that maximizes τy(t) subject to t ∈ [a,b] and τx(t) = x. Without loss of generality, assume f(x) ≤ g(x). Let h(x) be τy(c(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))·δ + (bg(x))·δ ≥ ||τ(a)τ(f(x))||² + ||τ(f(x))τ(g(x))||² + ||τ(g(x))τ(b)||² = (r+x)² + τy(f(x))² + h(x)² + (rx)² + τ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 ∫rrh(x)dx gives us an upper bound on the two-dimensional measure of the points in the curve section under consideration. We have ∫rrh(x)dx ≤ (1/√3)∫rr2√(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, ba ≤ (1/√3)πr² and δ = ||τ(a)τ(b)||²/(ba) ≥ 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 / (16π) ≈ 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

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.

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 (mk−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 f1,…,fk 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 S1,…,Sk, such that Si contains the points of S in order of increasing image under fi. 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 S1,…,Sk. 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 fi such that its inverse fi−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 φ≤4(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 f1,…,fd 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?

1)
Swanwa Liao, Mario López, and Scott Leutenegger: High dimensional similarity search with space filling curves. ICDE 2001:615-622. Proof sketch: let p be a point in S, and let x be the distance to its nearest neighbour in S. For each recursion level r there is a permutation π such that cubes of width 2r at offset 2r·i/(d+1) (mod 2r) in all d coordinates are contiguous in the ordering induced by fπ(i); in particular if we choose r to be more than (2d+2)x and at most (4d+4)x. Since a point p has only d coordinates, there must an i such that all coordinates of p differ from 2r i/(d+1) by at least 2r/(2d+2) (mod 2r). Thus p is at distance at least 2r/(2d+2) > x from the boundary of a contiguous cube of width 2r in the ordering induced by fπ(i). The nearest neighbour to p in S lies in that same cube. So at least one of the neighbours of p in Sπ(i) also lies in that same cube and is a (4d+4)-approximation to the nearest neighbour of p in S.
unsolved_puzzles.txt · Last modified: 2018/07/29 08:30 by administrator