Provided by: libmath-planepath-perl_113-1_all 
NAME
Math::PlanePath::HIndexing -- self-similar right-triangle 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 the H-indexing by Rolf Niedermeier, Klaus Reinhardt
and Peter Sanders.
"Towards Optimal Locality In Mesh Indexings", Discrete Applied Mathematics, volume
117, March 2002. <http://theinf1.informatik.uni-jena.de/publications/dam01a.pdf>
It traverses an octant 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" 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.
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.
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
SEE ALSO
Math::PlanePath, Math::PlanePath::SierpinskiCurve
HOME PAGE
<http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE
Copyright 2011, 2012, 2013 Kevin Ryde
This 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/>.