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 H-indexing per
- Rolf Niedermeier, Klaus Reinhardt and Peter Sanders, ``Towards Optimal Locality In Mesh Indexings'', Discrete Applied Mathematics, volume 117, March 2002, pages 211-237. <http://theinf1.informatik.uni-jena.de/publications/dam01a.pdf>
It traverses an eighth of the plane by self-similar right triangles. Notice the ``H'' shapes that arise from the backtracking, for example N=8 to N=23, and repeating above it.
| |
15 | 63--64 67--68 75--76 79--80 111-112 115-116 123-124 127
| | | | | | | | | | | | | | | |
14 | 62 65--66 69 74 77--78 81 110 113-114 117 122 125-126
| | | | | | | |
13 | 61 58--57 70 73 86--85 82 109 106-105 118 121
| | | | | | | | | | | | | |
12 | 60--59 56 71--72 87 84--83 108-107 104 119-120
| | | |
11 | 51--52 55 40--39 88 91--92 99-100 103
| | | | | | | | | | | |
10 | 50 53--54 41 38 89--90 93 98 101-102
| | | | | |
9 | 49 46--45 42 37 34--33 94 97
| | | | | | | | | |
8 | 48--47 44--43 36--35 32 95--96
| |
7 | 15--16 19--20 27--28 31
| | | | | | | |
6 | 14 17--18 21 26 29--30
| | | |
5 | 13 10-- 9 22 25
| | | | | |
4 | 12--11 8 23--24
| |
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 4-point verticals like N=0 to N=3 are a Sierpinski horizontal, and the 4-point ``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 1--2 5--6 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^3-1=127 and X,Y ranging up to Xmax=2*2^3-2=14 and Xmax=2*2^3-1=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^k-1 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
- "($n_lo, $n_hi) = $path->level_to_n_range($level)"
- Return "(0, 2*4**$level - 1)".
FORMULAS
Area
The area enclosed by curve in its triangular level k is
A[k] = (2^k-1)^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^k-2 wide (eg. 2^2-2=2 wide in the k=2 above). Parts 2 and 3 have an area in between 1 wide 2^k-1 high (eg. 2^2-1=3 high in the k=2 above). So the total area is
A[k] = 4*A[k-1] + 2^k-2 + 2^k-1 starting A[0] = 0
= 4^0 * (2*2^k - 3)
+ 4^1 * (2*2^(k-1) - 3)
+ 4^2 * (2*2^(k-2) - 3)
+ ...
+ 4^(k-1) * (2*2^1 - 3)
+ 4^k * A[0]
= 2*2*(4^k - 2^k)/(4-2) - 3*(4^k - 1)/(4-1)
= (2^k - 1)^2
Half Level Areas
Block 1 ends at the top-left 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^k-2 or 2^k-1 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
| | @ |
12--11 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 15--16 19--20 27--28 31
| @ | | @ | | @ | | @ |
5-- 6 17--18 21 26 29--30
| @ |
22 25
| @ |
23--24
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^j-1, 2^j
A060867 area of level
A059153 area of level first half
A092440 area of level second half
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015, 2016 Kevin RydeThis file is part of Math-PlanePath.
Math-PlanePath 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.
Math-PlanePath 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 Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.