Pierre CagneAppalachian State

Research · Bachelor internship · 2011

Local configurations of discrete planes

My bachelor research internship at LORIA (Nancy), in the ADAGIo team, supervised by Damien Jamet and Éric Domenjoud: counting and generating the local configurations of naive discrete planes. The report tells the whole story, in French. This page shows the objects it studies, and serves the programs written for it, which are documented and commented in English.

The (m,n)-cubes

A naive plane is a plane drawn with unit cubes: the integer points (x, y, z) with z = −⌊αx + βy + μ⌋, where the slopes α and β lie in ]0, 1[ and the offset μ in [0, 1[. Its (m,n)-cubes are what it looks like through a window of m × n columns, up to translation. The internship counted them, and generated them.

The cube at (x, y) of a plane is the cube at the origin of the plane with the same slopes and the offset {αx + βy + μ}, the fractional part of αx + βy + μ, so it is enough to look at the origin. There, the cube is the matrix of the depths ⌊iα + jβ + μ⌋, for 0 ≤ i < m and 0 ≤ j < n. For a fixed offset, these depths change exactly when (α, β) crosses one of the lines iα + jβ + μ ∈ ℤ. These lines cut the square of slopes into the faces of a graph Gμm,n, one face for each (m,n)-cube at the origin of the planes with offset μ. The programs below count these faces, or walk through them to list the cubes.

Letting the offset vary too, the planes iα + jβ + μ = k cut the cube of parameters (α, β, μ) into chambers: this is the cube dual G of the report's section 4.2. Each chamber is one (m,n)-cube, and Gμm,n is the slice of G at height μ. Watching the faces appear and disappear as the slice moves up counts all the cubes.

Choose m, n and the offset μ, then click a face of Gμm,n to see its cube; you can also drag the amber point, or move it with the arrow keys once the square has the focus. As in the report, the vertical lines (j = 0) are red, the horizontal ones (i = 0) green, and the oblique ones blue, fainter as i + j grows. The cube is drawn with voxels, a depth of 1 one step below a depth of 0. Below, the chamber of that cube in G: drag it to turn it. The slider stops at every offset where the number of faces can change, and once between each two.

Programs

Each archive contains the sources and a README explaining how to build the documentation locally, in HTML and PDF. The HTML documentation is also online, with the source code pretty-printed for the first three programs.

  1. 1

    Counting the (m,n)-cubes at (0,0) of a naive plane with zero offset

    Computes the cardinality of M0m,n.

  2. 2

    Counting all the (m,n)-cubes

    Computes the cardinality of Mm,n. It differs from the first program in that it accepts a rational offset μ; the Perl script then counts all the (m,n)-cubes.

  3. 3

    Generating the (m,n)-cubes at (0,0) of a naive plane with zero offset

    Generates the two-dimensional Rote sequences of the elements of M0m,n.

  4. 4

    Counting the (m,n)-cubes at (0,0) with zero offset: the reduced graph method

    Computes the cardinality of M0m,n another way.

Scripts for figures

A few Perl scripts written for the report. They generate LaTeX code for TikZ, and are a good way to see the objects of the internship.

  1. pl

    graph.pl

    Takes m, n, μ and a scale, and draws the graph Gμm,n of the report. A scale of 6 fits an A4 page.

  2. pl

    tikz_cubes.pl

    Reads the output of the generation program and draws the cubes from their Rote sequences.

  3. pl

    tikz_plan.pl

    Takes v1, v2, v3, μ, m, n and a unit, and draws the (m,n)-pattern at (0,0) of the naive plane with normal vector (v1, v2, v3) and offset μ. The unit, in points, is the edge length of a voxel.