Math::...dexing(3pm)

📦
version 129 · 3 versions
, in debian bookworm, debian trixie, ubuntu jammy, ubuntu noble, ubuntu resolute, ubuntu stonking

💖 Math::PlanePath::HIndexing 💖

okay bestie, gather round, because we're about to get into a self-similar right-triangle traversal and it is lowkey gorgeous. This is the Math::PlanePath::HIndexing page from the User Contributed Perl Documentation, and yes it's giving very much math-girlie era. 🦋

✨ NAME ✨

Math::PlanePath::HIndexing — self-similar right-triangle traversal 💅

🌸 SYNOPSIS 🌸

like, here's the vibe, fr fr:

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

🎀 DESCRIPTION 🎀

so this is an infinite integer version of H-indexing, per this absolute icon of a paper:

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. and the way it backtracks creates literal "H" shapes?? obsessed. look at N=8 to N=23, and then it repeats above it. no cap, it's H's all the way up.

    |                                                           |
 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). Here's the same energy but with two points per triangle. Or honestly you could also think of it as those triangles further divided so there's one point each, just a little skewed. same vibe, different styling 💖

+---------+---------+--------+--------/
|  \      |      /  | \      |       /
| 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  /
|  /
+/

and the correspondence to the SierpinskiCurve path goes like this, bestie: 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 a bit of stretching. iconic behavior honestly.

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, she stays as she is 💅). For example Y=10 decimal is 1010 binary, duplicate to binary 1100110 which is N=102. slay.

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, periodt.

🫶 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. new bestie unlocked ✨
  • ($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. (she simply will not engage 😭)

🧚 Level Methods 🧚

  • ($n_lo, $n_hi) = $path->level_to_n_range($level) — return (0, 2*4**$level - 1).

🔥 FORMULAS 🔥

💜 Area 💜

The area enclosed by the 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 and 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 starts 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)

A334235    X coordinate
A334236    Y coordinate
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

👑 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/>.

⚠️ okay so the license bit is the serious part: no warranty, no promises, read the GPL, that's the whole deal. respect the copyright, bestie. 🙈

aaaand that's the whole page!! this was documented in perl v5.32.0 on 2021-01-23, and the manual name for it is Math::...dexing(3pm) 🎀 thanks for reading, mwah, go draw some H shapes 💜

📦 where this page comes from