Cross polytopes

How to enumerate the surface points of a cross polytope laying on a multidimensional grid:

#!/usr/bin/perl

sub enumerate {
    my ($d, $r) = @_;

    if ($d == 1) {
        return ($r ? ([-$r], [$r]) : [0])
    }
    else {
        my @r;
        for my $i (0..$r) {
            for my $s (enumerate($d - 1, $r - $i)) {
                for my $j ($i ? (-$i, $i) : 0) {
                    push @r, [@$s, $j]
                }
            }
        }
        return @r;
    }
}

@ARGV == 2 or die "Usage:\n  $0 dimension radius\n\n";
my ($d, $r) = @ARGV;

my @r = enumerate($d, $r);
print "[", join(',', @$_), "]\n" for @r;

This comes from this StackOverflow question. Initially I overlooked the paragraph where it states that the Manhattan distance is going to be used, so I solved it for the hypersphere defined using the euclidean distance.

BTW, the cross polytope is the euclidean-space equivalent of the n-sphere on the Manhattan-space.

This script enumerates the grid points in the n-ball (not just the surface of the n-sphere):


#!/usr/bin/perl

use strict;
use warnings;
use POSIX 'floor';

sub enumerate {
    my ($d, $r2) = @_;
    my $l = floor sqrt $r2;
    if ($d == 1) {
        return map [$_], -$l..$l;
    }
    else {
        my @r;
        for my $i (-$l..$l) {
            my @s = enumerate($d - 1, $r2 - $i * $i);
            push @$_, $i for @s;
            push @r, @s;
        }
        return @r;
    }
}

@ARGV == 2 or die "Usage:\n  $0 dimension radius\n\n";
my ($d, $r) = @ARGV;

my @r = enumerate($d, $r * $r);
print "[", join(',', @$_), "]\n" for @r;


Well, the most interesting thing about that is that I have never noticed before that the cross-polytope is a generalization of the square into higher dimensions. Until now, my mind had always followed the sequence segment, square, cube, hypercube.

But, segment, square, octahedron, cross-polytope is also possible!!!