NAME
Math::PlanePath::HIndexing  selfsimilar righttriangle traversal
SYNOPSIS
use Math::PlanePath::HIndexing;
my $path = Math::PlanePath::HIndexing>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This is an infinite integer version of Hindexing per
Rolf Niedermeier, Klaus Reinhardt and Peter Sanders, "Towards Optimal Locality In Mesh Indexings", Discrete Applied Mathematics, volume 117, March 2002, pages 211237. http://theinf1.informatik.unijena.de/publications/dam01a.pdf
It traverses an eighth of the plane by selfsimilar right triangles. Notice the "H" shapes that arise from the backtracking, for example N=8 to N=23, and repeating above it.
 
15  6364 6768 7576 7980 111112 115116 123124 127
               
14  62 6566 69 74 7778 81 110 113114 117 122 125126
       
13  61 5857 70 73 8685 82 109 106105 118 121
             
12  6059 56 7172 87 8483 108107 104 119120
   
11  5152 55 4039 88 9192 99100 103
           
10  50 5354 41 38 8990 93 98 101102
     
9  49 4645 42 37 3433 94 97
         
8  4847 4443 3635 32 9596
 
7  1516 1920 2728 31
       
6  14 1718 21 26 2930
   
5  13 10 9 22 25
     
4  1211 8 2324
 
3  3 4 7
   
2  2 5 6
 
1  1
 
Y=0  0
+
X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
The tiling is essentially the same as the Sierpinski curve (see Math::PlanePath::SierpinskiCurve). The following is with two points per triangle. Or equally well it could be thought of with those triangles further divided to have one point each, a little skewed.
++++/
 \  /  \  /
 15 \ 16 19 /20 27\ 28 31 /
  \   /    \    /
 14 \17 18/ 21 26 \29 30 /
 \  /  \  /
+++/
 /  \  /
 13 /10  9 \ 22  25 /
  /    \    /
 12/ 11  8 \23  24/
 /  \  /
+/
 \  /
 3 \ 4  7 /
  \    /
 2 \ 5  6 /
 \  /
+/
 /
 1 /
  /
 0 /
 /
+/
The correspondence to the SierpinskiCurve
path is as follows. The 4point verticals like N=0 to N=3 are a Sierpinski horizontal, and the 4point "U" parts like N=4 to N=7 are a Sierpinski vertical. In both cases there's an X,Y transpose and bit of stretching.
3 7
 /
2 12 56 6
 <=> / \   <=> 
1 0 3 4 7 5
 \
0 4
Level Ranges
Counting the initial N=0 to N=7 section as level 1, the X,Y ranges for a given level is
Nlevel = 2*4^level  1
Xmax = 2*2^level  2
Ymax = 2*2^level  1
For example level=3 is N through to Nlevel=2*4^31=127 and X,Y ranging up to Xmax=2*2^32=14 and Xmax=2*2^31=15.
On even Y rows, the N on the X=Y diagonal is found by duplicating each bit in Y except the low zero (which is unchanged). For example Y=10 decimal is 1010 binary, duplicate to binary 1100110 is N=102.
It would be possible to take a level as N=0 to N=4^k1 too, which would be a triangle against the Y axis. The 2*4^level  1 is per the paper above.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::HIndexing>new ()

Create and return a new path object.
($x,$y) = $path>n_to_xy ($n)

Return the X,Y coordinates of point number
$n
on the path. Points begin at 0 and if$n < 0
then the return is an empty list.
Level Methods
FORMULAS
Area
The area enclosed by curve in its triangular level k is
A[k] = (2^k1)^2
= 0, 1, 9, 49, 225, 961, 3969, 16129, ... (A060867)
For example level k=2 enclosed area marked by "@" signs,
7  ******31
   @   @   @ 
6  * ** * * **
   @ 
5  * ** * *
   @   @ 
4  ** * ** level k=2
  @ @  N=0 to N=31
3  * * *
   @  A[2] = 9
2  * * *
 
1  *
 
Y=0  0
+
X=0 1 2 3 4 5 6
The block breakdowns are
++ ^
 \ ^   ^ / 
\ \ 2   3 /  = 2^k  1
 \ \   / 
 1\ \   / 
 v \ \++/ v
++
 
++
 ^ /
 0 /
 /
 /
+/
<> = 2^k  2
Parts 0 and 3 are identical. Parts 1 and 2 are mirror images of 0 and 3 respectively. Parts 0 and 1 have an area in between 1 high and 2^k2 wide (eg. 2^22=2 wide in the k=2 above). Parts 2 and 3 have an area in between 1 wide 2^k1 high (eg. 2^21=3 high in the k=2 above). So the total area is
A[k] = 4*A[k1] + 2^k2 + 2^k1 starting A[0] = 0
= 4^0 * (2*2^k  3)
+ 4^1 * (2*2^(k1)  3)
+ 4^2 * (2*2^(k2)  3)
+ ...
+ 4^(k1) * (2*2^1  3)
+ 4^k * A[0]
= 2*2*(4^k  2^k)/(42)  3*(4^k  1)/(41)
= (2^k  1)^2
Half Level Areas
Block 1 ends at the topleft corner and block 2 start there. The area before that midpoint enclosed to the Y axis can be calculated. Likewise the area after that midpoint to the top line. Both are two blocks, and with either 2^k2 or 2^k1 in between. They're therefore half the total area A[k], with the extra unit square going to the top AT[k].
AY[k] = floor(A[k]/2)
= 0, 0, 4, 24, 112, 480, 1984, 8064, 32512, ... (A059153)
AT[k] = ceil(A[k]/2)
= 0, 1, 5, 25, 113, 481, 1985, 8065, 32513, ... (A092440)
15

14

13 10 9
  @ 
1211 8
@ @ 
3 3 4 7
   @ 
2 2 5 6
 
1 1
 
0 0 0
AY[0] = 0 AY[1] = 0 AY[2] = 4
1 3 4 7 1516 1920 2728 31
 @   @   @   @ 
5 6 1718 21 26 2930
 @ 
22 25
 @ 
2324
AT[0] = 0 AT[1] = 1 AT[2] = 5
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
http://oeis.org/A097110 (etc)
A097110 Y at N=2^k, being successively 2^j1, 2^j
A060867 area of level
A059153 area of level first half
A092440 area of level second half
SEE ALSO
Math::PlanePath, Math::PlanePath::SierpinskiCurve
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
MathPlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with MathPlanePath. If not, see <http://www.gnu.org/licenses/>.