5 ms·

Mathematically, I would phrase this by saying that the mapping of physical location to (lat,lon) pair is continuous. Space-filling curves and related things lik

Mathematically, I would phrase this by saying that the mapping of physical location to (lat,lon) pair is continuous. Space-filling curves and related things like Google's plus codes are nearly as good, in that (if you squint) they are continuous almost everywhere (everywhere but the boundary of some grid). W3W on the other hand is discontinuous everywhere. I think the advantage of lat/lon boils down to the fact that everyone knows 79.999 is close to 80.000, even though they look quite different as raw text.

ltbarcly3 8y ago
So you have to be careful with the terminology. Space filling curves can be a continuous mapping of the line to the curve itself. However, this does not set up a continuous mapping from the space to the coordinate system, which is also quite important. A tiny change in your coordinate will mean a tiny change in your physical position, but a tiny change in your physical position will almost always mean a quite large (and basically not predictable without doing an involved calculation) change in your coordinate.
- kevinventullo 8y ago
  Yeah, let me try to be more precise, though maybe it's worth writing down in a more formal setting because comments are awkward. Say we're looking at the Hilbert curve. I claim that for almost all physical positions, a sufficiently small change in position yields a correspondingly small change in coordinate. In the purely mathematical sense, this means something like "continuous except at points with at least one rational coordinate". In the programming sense, where everything must be approximated and you're mapping a 2-d lattice to a 1-d lattice, then it's a bit tricky to formulate, but something like: if you take the maximum distance in 1-d space between a 2-d point and its eight "neighbors", then the probability of this distance being > N should be O(1/sqrt(N)). Concretely, P(point has an adjacent point whose Hilbert coordinate disagrees past the highest n bits) == P(d > 4^n) < 4*(1/2)^n
  - ltbarcly3 8y ago
    I took a 256 square hilbert curve and took random points in it (discarding points where the euclidian distance was > 8). Here is the plot: https://gist.github.com/justinvanwinkle/22a15bb33536095b05dc9f68a87e2754 https://gist.github.com/justinvanwinkle/22a15bb33536095b05dc... Notice the Log y axis. I don't you think you could consider this even roughly continuous. This is only even bounded because I only took points within the 256x256 grid, if I let it run over say a 1000x1000 grid the hilbert distances wouldn't plot well even on a log plot. The second plot I took any random point within euclidian distance 8 from a random first point, and didn't restrict it to stay in the same 256x256 grid. 10k points total. Even at distance 1, you get hilbert distances like: 4469269309980865699858008332735282042493121940197464459241187147907254676691182325600624766055634475896677286062162016951251294270648856648811216335320387
    - kevinventullo 8y ago
      I'm not sure why that first plot wouldn't be considered continuous. There's a pretty clear positive correlation, which should be more pronounced with a non-log scale y-axis, and more pronounced as you increase the order of the curve. I'm confused about the second plot; what order is the curve? It seems weird that there are no points between 10^12 and 10^156.
      - ltbarcly3 8y ago
        The second graph has a huge jump because the left side of the area I'm taking points from is a boundary between two very distant parts of the curve. In any space filling curve you will be able to find arbitrarily large jumps like this. The difference would be more pronounced on a non-log scale, except the huge numbers at the top of the range would squish the graph down so you couldn't see what was going on. The first graph isn't just not continuous, it's not even 1-1. (I'm ignoring the fact that is also discrete so that any formal sense of 'continuity' can't exist. Even if you tried to make it continuous by filling in the gaps it would be impossible.)
        8y ago

ltbarcly3 8y ago

So you have to be careful with the terminology. Space filling curves can be a continuous mapping of the line to the curve itself. However, this does not set up a continuous mapping from the space to the coordinate system, which is also quite important. A tiny change in your coordinate will mean a tiny change in your physical position, but a tiny change in your physical position will almost always mean a quite large (and basically not predictable without doing an involved calculation) change in your coordinate.

kevinventullo 8y ago
Yeah, let me try to be more precise, though maybe it's worth writing down in a more formal setting because comments are awkward. Say we're looking at the Hilbert curve. I claim that for almost all physical positions, a sufficiently small change in position yields a correspondingly small change in coordinate. In the purely mathematical sense, this means something like "continuous except at points with at least one rational coordinate". In the programming sense, where everything must be approximated and you're mapping a 2-d lattice to a 1-d lattice, then it's a bit tricky to formulate, but something like: if you take the maximum distance in 1-d space between a 2-d point and its eight "neighbors", then the probability of this distance being > N should be O(1/sqrt(N)). Concretely, P(point has an adjacent point whose Hilbert coordinate disagrees past the highest n bits) == P(d > 4^n) < 4*(1/2)^n
- ltbarcly3 8y ago
  I took a 256 square hilbert curve and took random points in it (discarding points where the euclidian distance was > 8). Here is the plot: https://gist.github.com/justinvanwinkle/22a15bb33536095b05dc9f68a87e2754 https://gist.github.com/justinvanwinkle/22a15bb33536095b05dc... Notice the Log y axis. I don't you think you could consider this even roughly continuous. This is only even bounded because I only took points within the 256x256 grid, if I let it run over say a 1000x1000 grid the hilbert distances wouldn't plot well even on a log plot. The second plot I took any random point within euclidian distance 8 from a random first point, and didn't restrict it to stay in the same 256x256 grid. 10k points total. Even at distance 1, you get hilbert distances like: 4469269309980865699858008332735282042493121940197464459241187147907254676691182325600624766055634475896677286062162016951251294270648856648811216335320387
  - kevinventullo 8y ago
    I'm not sure why that first plot wouldn't be considered continuous. There's a pretty clear positive correlation, which should be more pronounced with a non-log scale y-axis, and more pronounced as you increase the order of the curve. I'm confused about the second plot; what order is the curve? It seems weird that there are no points between 10^12 and 10^156.
    - ltbarcly3 8y ago
      The second graph has a huge jump because the left side of the area I'm taking points from is a boundary between two very distant parts of the curve. In any space filling curve you will be able to find arbitrarily large jumps like this. The difference would be more pronounced on a non-log scale, except the huge numbers at the top of the range would squish the graph down so you couldn't see what was going on. The first graph isn't just not continuous, it's not even 1-1. (I'm ignoring the fact that is also discrete so that any formal sense of 'continuity' can't exist. Even if you tried to make it continuous by filling in the gaps it would be impossible.)
      - 8y ago