1Math::PlanePath::HIndexUisnegr(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::HIndexing(3)
2
3
4

NAME

6       Math::PlanePath::HIndexing -- self-similar right-triangle traversal
7

SYNOPSIS

9        use Math::PlanePath::HIndexing;
10        my $path = Math::PlanePath::HIndexing->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This is an infinite integer version of H-indexing per
15
16           Rolf Niedermeier, Klaus Reinhardt and Peter Sanders, "Towards
17           Optimal Locality In Mesh Indexings", Discrete Applied Mathematics,
18           volume 117, March 2002, pages 211-237.
19           <http://theinf1.informatik.uni-jena.de/publications/dam01a.pdf>
20
21       It traverses an eighth of the plane by self-similar right triangles.
22       Notice the "H" shapes that arise from the backtracking, for example N=8
23       to N=23, and repeating above it.
24
25               |                                                           |
26            15 |  63--64  67--68  75--76  79--80 111-112 115-116 123-124 127
27               |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
28            14 |  62  65--66  69  74  77--78  81 110 113-114 117 122 125-126
29               |   |           |   |           |   |           |   |
30            13 |  61  58--57  70  73  86--85  82 109 106-105 118 121
31               |   |   |   |   |   |   |   |   |   |   |   |   |   |
32            12 |  60--59  56  71--72  87  84--83 108-107 104 119-120
33               |           |           |                   |
34            11 |  51--52  55  40--39  88  91--92  99-100 103
35               |   |   |   |   |   |   |   |   |   |   |   |
36            10 |  50  53--54  41  38  89--90  93  98 101-102
37               |   |           |   |           |   |
38             9 |  49  46--45  42  37  34--33  94  97
39               |   |   |   |   |   |   |   |   |   |
40             8 |  48--47  44--43  36--35  32  95--96
41               |                           |
42             7 |  15--16  19--20  27--28  31
43               |   |   |   |   |   |   |   |
44             6 |  14  17--18  21  26  29--30
45               |   |           |   |
46             5 |  13  10-- 9  22  25
47               |   |   |   |   |   |
48             4 |  12--11   8  23--24
49               |           |
50             3 |   3-- 4   7
51               |   |   |   |
52             2 |   2   5-- 6
53               |   |
54             1 |   1
55               |   |
56           Y=0 |   0
57               +-------------------------------------------------------------
58                  X=0  1   2   3   4   5   6   7   8   9  10  11  12  13  14
59
60       The tiling is essentially the same as the Sierpinski curve (see
61       Math::PlanePath::SierpinskiCurve).  The following is with two points
62       per triangle.  Or equally well it could be thought of with those
63       triangles further divided to have one point each, a little skewed.
64
65           +---------+---------+--------+--------/
66           |  \      |      /  | \      |       /
67           | 15 \  16| 19  /20 |27\  28 |31    /
68           |  |  \  ||  | /  | | | \  | | |  /
69           | 14   \17| 18/  21 |26  \29 |30 /
70           |       \ | /       |     \  |  /
71           +---------+---------+---------/
72           |       / |  \      |       /
73           | 13  /10 | 9 \  22 | 25   /
74           |  | /  | | |  \  | |  |  /
75           | 12/  11 | 8   \23 | 24/
76           |  /      |      \  |  /
77           +-------------------/
78           |  \      |       /
79           | 3 \   4 | 7    /
80           | |  \  | | |  /
81           | 2   \ 5 | 6 /
82           |       \ |  /
83           +----------/
84           |         /
85           | 1     /
86           | |   /
87           | 0  /
88           |  /
89           +/
90
91       The correspondence to the "SierpinskiCurve" path is as follows.  The
92       4-point verticals like N=0 to N=3 are a Sierpinski horizontal, and the
93       4-point "U" parts like N=4 to N=7 are a Sierpinski vertical.  In both
94       cases there's an X,Y transpose and bit of stretching.
95
96           3                                       7
97           |                                      /
98           2         1--2             5--6       6
99           |  <=>   /    \            |  |  <=>  |
100           1       0      3           4  7       5
101           |                                      \
102           0                                       4
103
104   Level Ranges
105       Counting the initial N=0 to N=7 section as level 1, the X,Y ranges for
106       a given level is
107
108           Nlevel = 2*4^level - 1
109           Xmax = 2*2^level - 2
110           Ymax = 2*2^level - 1
111
112       For example level=3 is N through to Nlevel=2*4^3-1=127 and X,Y ranging
113       up to Xmax=2*2^3-2=14 and Xmax=2*2^3-1=15.
114
115       On even Y rows, the N on the X=Y diagonal is found by duplicating each
116       bit in Y except the low zero (which is unchanged).  For example Y=10
117       decimal is 1010 binary, duplicate to binary 1100110 is N=102.
118
119       It would be possible to take a level as N=0 to N=4^k-1 too, which would
120       be a triangle against the Y axis.  The 2*4^level - 1 is per the paper
121       above.
122

FUNCTIONS

124       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
125       classes.
126
127       "$path = Math::PlanePath::HIndexing->new ()"
128           Create and return a new path object.
129
130       "($x,$y) = $path->n_to_xy ($n)"
131           Return the X,Y coordinates of point number $n on the path.  Points
132           begin at 0 and if "$n < 0" then the return is an empty list.
133
134   Level Methods
135       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
136           Return "(0, 2*4**$level - 1)".
137

FORMULAS

139   Area
140       The area enclosed by curve in its triangular level k is
141
142           A[k] = (2^k-1)^2
143                = 0, 1, 9, 49, 225, 961, 3969, 16129, ...  (A060867)
144
145       For example level k=2 enclosed area marked by "@" signs,
146
147             7 |   *---*---*---*---*---*---31
148               |   |   | @ |   | @ |   | @ |
149             6 |   *   *---*   *   *   *---*
150               |   |           | @ |
151             5 |   *   *---*   *   *
152               |   |   | @ |   | @ |
153             4 |   *---*   *   *---*         level k=2
154               |   | @   @ |                 N=0 to N=31
155             3 |   *-- *   *
156               |   |   | @ |                 A[2] = 9
157             2 |   *   *-- *
158               |   |
159             1 |   *
160               |   |
161           Y=0 |   0
162               +------------------------------
163                  X=0  1   2   3   4   5   6
164
165       The block breakdowns are
166
167           +---------------+     ^
168           | \  ^ |  | ^  /      |
169           |\ \ 2 |  | 3 /       | = 2^k - 1
170           | \ \  |  |  /        |
171           | 1\ \ |  | /         |
172           | v \ \+--+/          v
173           +----+
174           |    |
175           +----+
176           | ^  /
177           | 0 /
178           |  /
179           | /
180           +/
181
182           <---->  = 2^k - 2
183
184       Parts 0 and 3 are identical.  Parts 1 and 2 are mirror images of 0 and
185       3 respectively.  Parts 0 and 1 have an area in between 1 high and 2^k-2
186       wide (eg. 2^2-2=2 wide in the k=2 above).  Parts 2 and 3 have an area
187       in between 1 wide 2^k-1 high (eg. 2^2-1=3 high in the k=2 above).  So
188       the total area is
189
190           A[k] = 4*A[k-1] + 2^k-2 + 2^k-1     starting A[0] = 0
191                =    4^0     * (2*2^k - 3)
192                   + 4^1     * (2*2^(k-1) - 3)
193                   + 4^2     * (2*2^(k-2) - 3)
194                   + ...
195                   + 4^(k-1) * (2*2^1 - 3)
196                   + 4^k * A[0]
197                = 2*2*(4^k - 2^k)/(4-2) - 3*(4^k - 1)/(4-1)
198                = (2^k - 1)^2
199
200   Half Level Areas
201       Block 1 ends at the top-left corner and block 2 start there.  The area
202       before that midpoint enclosed to the Y axis can be calculated.
203       Likewise the area after that midpoint to the top line.  Both are two
204       blocks, and with either 2^k-2 or 2^k-1 in between.  They're therefore
205       half the total area A[k], with the extra unit square going to the top
206       AT[k].
207
208           AY[k] = floor(A[k]/2)
209                 = 0, 0, 4, 24, 112, 480, 1984, 8064, 32512, ...  (A059153)
210
211           AT[k] = ceil(A[k]/2)
212                 = 0, 1, 5, 25, 113, 481, 1985, 8065, 32513, ...  (A092440)
213
214                                            15
215                                             |
216                                            14
217                                             |
218                                            13  10-- 9
219                                             |   | @ |
220                                            12--11   8
221                                               @   @ |
222                             3               3-- 4   7
223                             |               |   | @ |
224                             2               2   5-- 6
225                             |               |
226                             1               1
227                             |               |
228               0             0               0
229
230           AY[0] = 0     AY[1] = 0       AY[2] = 4
231
232              1       3-- 4   7       15--16  19--20  27--28  31
233                          | @ |            | @ |   | @ |   | @ |
234                          5-- 6           17--18  21  26  29--30
235                                                   | @ |
236                                                  22  25
237                                                   | @ |
238                                                  23--24
239
240           AT[0] = 0   AT[1] = 1      AT[2] = 5
241

OEIS

243       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
244       this path include
245
246           <http://oeis.org/A097110> (etc)
247
248           A334235    X coordinate
249           A334236    Y coordinate
250           A097110    Y at N=2^k, being successively 2^j-1, 2^j
251
252           A060867    area of level
253           A059153    area of level first half
254           A092440    area of level second half
255

SEE ALSO

257       Math::PlanePath, Math::PlanePath::SierpinskiCurve
258

HOME PAGE

260       <http://user42.tuxfamily.org/math-planepath/index.html>
261

LICENSE

263       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
264       Kevin Ryde
265
266       This file is part of Math-PlanePath.
267
268       Math-PlanePath is free software; you can redistribute it and/or modify
269       it under the terms of the GNU General Public License as published by
270       the Free Software Foundation; either version 3, or (at your option) any
271       later version.
272
273       Math-PlanePath is distributed in the hope that it will be useful, but
274       WITHOUT ANY WARRANTY; without even the implied warranty of
275       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
276       General Public License for more details.
277
278       You should have received a copy of the GNU General Public License along
279       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
280
281
282
283perl v5.34.0                      2021-07-22     Math::PlanePath::HIndexing(3)
Impressum