4
$\begingroup$

The Hilbert curve is a continuous space-filling curve that maps $I$ to $I^n$ where $I$ denotes the unit interval [1]. Like all other space-filling curves, it is not one-to-one. I am wondering if the Hilbert curve, or a common variant thereof, becomes a continuous bijective map if we restrict its domain/range to $\mathbb{CN} \mapsto \mathbb{CN}^n$ where $\mathbb{CN} \subset I$ denotes the set of computable numbers that lie within the unit interval.

At first glance, this seems like a true statement because we have the following two algorithms [2]:

  • A forward algorithm that takes any number $t \in \mathbb{CN}$ as input, iterates over its binary digits, and sequentially produces the binary digits of all numbers in a corresponding (unique) tuple $T \in \mathbb{CN}^n$.
  • A reverse algorithm that takes any tuple $T \in \mathbb{CN}^n$ as input, (simultaneously) iterates over the binary digits of $T$'s elements, and sequentially produces the binary digits of a (unique) number $t \in \mathbb{CN}$.

However, I'm not sure if this simple reasoning neglects to account for any of the finer points in computable analysis, especially with respect to the curve's continuity.

[1] As Pietro Majer points out, the original Hilbert curve maps $I$ to $I^2$. In this question, I am referring to its standard n-dimensional extension that uses Gray codes to construct its finite approximations.

[2] The algorithms I mention above is described here. As far as I can tell, these algorithms operate on the standard n-dimensional Hilbert curve (and utilize Gray codes to construct outputs from given inputs).

Thanks in advance for any comments, ideas and pointers to the relevant literature.

Improve this question
$\endgroup$
16
  • 1
    $\begingroup$ Injectivity depends on the curve of course - maybe the original curve maps two computable points to the same element. I think the "right" question here is whether some Hilbert curve which is computable is injective on the computable points. $\endgroup$
    – Noah Schweber
    Commented Dec 25, 2019 at 20:40
  • 1
    $\begingroup$ I believe the standard curve is not injective on computable points - intuitively, we can find many non-injectivities pretty easily, and this suggests that those non-injectivities are computable. $\endgroup$
    – Noah Schweber
    Commented Dec 25, 2019 at 20:56
  • 2
    $\begingroup$ For example, in this Hilbert curve: en.wikipedia.org/wiki/Hilbert_curve the midpoint $(1/2,1/2)$is the image of three different points, all computable. $\endgroup$
    – Gerald Edgar
    Commented Dec 26, 2019 at 12:31
  • 1
    $\begingroup$ @PietroMajer: I mean the n-dimensional generalization that uses Gray codes. I added this to the question body. $\endgroup$
    – Mehmet Ozan Kabak
    Commented Dec 26, 2019 at 14:13
  • 2
    $\begingroup$ Where am I going wrong? The number $1/2$ has more than one binary expansion. Not only $0.10000\cdots$ but also $0.01111\cdots$. $\endgroup$
    – Gerald Edgar
    Commented Dec 26, 2019 at 14:41

1 Answer 1

Reset to default
6
$\begingroup$

The Hilbert curve, due to its fractal nature, is mapping certain subintervals of the unit interval to certain squares in the unit square. On any given resolution, we have a bijection between the subintervals we consider on that scale, and the squares we consider at that scale. The non-injectivity of the actual map then comes from the fact that the intervals intersect in at most one point, whereas the squares can have an entire line as intersection.

Given any fractal space filling curve with these properties, we can compute two distinct points in the interval that get mapped to the same point in the unit square: Pick two non-adjacent intervals that get mapped to adjacent squares, and decide that our target points will be in these. On the next scale, there have to be matching subintervals/squares, and so on. The intersections of the intervals/squares yield points which are computable relative to the original space filling curve.

We thus see that a computable Hilbert curve is a never a bijection on the computable points.

However, given the curve and a point in the square, we can follow the bijections between squares and intervals back to compute some point in its preimage. Hence, the inverse of a computable Hilbert curve is not a function, but it is computable as a multivalued function.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I would like to check if I understand your argument correctly. If we find a point $(x, y)$ that always lies on the boundary of multiple squares regardless of the scale, and if at least one such square maps to an interval that is disjoint from the rest; then this point should be a non-injective point. Do I understand you correctly? If so, consider the two-dimensional curve and the point $(x, y) = (0.5, 0.25)$. If I'm not missing something, this point satisfies our condition. Do you think this point is a non-injective point? $\endgroup$
    – Mehmet Ozan Kabak
    Commented Dec 26, 2019 at 9:37
  • 1
    $\begingroup$ Let's go for (0.5,0.75) instead. This point belongs to the top-left square and to the top-right square on the first level. The top-left square is the image of [0;0.25] and the top-right square is the image of [0.75;1]. So (0.5,0.75) has a preimage in [0;0.25] and one in [0.75;1], so the curve definitely not injective there. Moreover, we can compute a preimage of (0.5,0.75) in each of the two intervals, so restricting to computable points doesn't change anything. $\endgroup$
    – Arno
    Commented Dec 26, 2019 at 16:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .