1Math::PlanePath::HIndexUisnegr(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::HIndexing(3)
2
6 Math::PlanePath::HIndexing -- self-similar right-triangle traversal
7
9 use Math::PlanePath::HIndexing;
10 my $path = Math::PlanePath::HIndexing->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is an infinite integer version of H-indexing per
15 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 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 | |
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 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 +---------+---------+--------+--------/
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 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 3 7
97 | /
98 2 1--2 5--6 6
99 | <=> / \ | | <=> |
100 1 0 3 4 7 5
101 | \
102 0 4
103 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 Nlevel = 2*4^level - 1
109 Xmax = 2*2^level - 2
110 Ymax = 2*2^level - 1
111 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 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 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
124 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
125 classes.
126 "$path = Math::PlanePath::HIndexing->new ()"
128 Create and return a new path object.
129 "($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 Level Methods
135 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
136 Return "(0, 2*4**$level - 1)".
137
139 Area
140 The area enclosed by curve in its triangular level k is
141 A[k] = (2^k-1)^2
143 = 0, 1, 9, 49, 225, 961, 3969, 16129, ... (A060867)
144 For example level k=2 enclosed area marked by "@" signs,
146 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 The block breakdowns are
166 +---------------+ ^
168 | \ ^ | | ^ / |
169 |\ \ 2 | | 3 / | = 2^k - 1
170 | \ \ | | / |
171 | 1\ \ | | / |
172 | v \ \+--+/ v
173 +----+
174 | |
175 +----+
176 | ^ /
177 | 0 /
178 | /
179 | /
180 +/
181 <----> = 2^k - 2
183 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 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 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 AY[k] = floor(A[k]/2)
209 = 0, 0, 4, 24, 112, 480, 1984, 8064, 32512, ... (A059153)
210 AT[k] = ceil(A[k]/2)
212 = 0, 1, 5, 25, 113, 481, 1985, 8065, 32513, ... (A092440)
213 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 AY[0] = 0 AY[1] = 0 AY[2] = 4
231 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 AT[0] = 0 AT[1] = 1 AT[2] = 5
241
243 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
244 this path include
245 <http://oeis.org/A097110> (etc)
247 A097110 Y at N=2^k, being successively 2^j-1, 2^j
249 A060867 area of level
251 A059153 area of level first half
252 A092440 area of level second half
253
255 Math::PlanePath, Math::PlanePath::SierpinskiCurve
256
258 <http://user42.tuxfamily.org/math-planepath/index.html>
259
261 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
262 This file is part of Math-PlanePath.
264 Math-PlanePath is free software; you can redistribute it and/or modify
266 it under the terms of the GNU General Public License as published by
267 the Free Software Foundation; either version 3, or (at your option) any
268 later version.
269 Math-PlanePath is distributed in the hope that it will be useful, but
271 WITHOUT ANY WARRANTY; without even the implied warranty of
272 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
273 General Public License for more details.
274 You should have received a copy of the GNU General Public License along
276 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
277perl v5.32.0 2020-07-28 Math::PlanePath::HIndexing(3)