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 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 - 1Xmax = 2*2^level - 2Ymax = 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
$non 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=313 | *-- * *| | | @ | A[2] = 92 | * *-- *| |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 0AY[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--24AT[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)
A334235 X coordinateA334236 Y coordinateA097110 Y at N=2^k, being successively 2^j-1, 2^jA060867 area of levelA059153 area of level first halfA092440 area of level second half
SEE ALSO
Math::PlanePath, Math::PlanePath::SierpinskiCurve
HOME PAGE
<http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 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/>.