This site is being phased out.

Euclidean space made discrete

From Mathematics Is A Science
Jump to navigationJump to search

Discretization of space

The need to discretize the Euclidean space comes from our desire to study the world computationally. The main examples of the successes of this idea are the following.

$\bullet$ Numerical methods of solving ordinary differential equations, starting with the Euler's method and other computations based on finite differences. Usually only the time (i.e., ${\bf R}$) is discretized:

Vector field R2 w sequence.png

$\bullet$ Numerical methods of partial differential equations and other simulations 2d and 3d behavior such as heat transfer, diffusion, wave propagation etc. This time the space is discretized as well:

Diffusion zoomed.png

$\bullet$ Digital imaging and image analysis, both black-and-white and color, both 2d and 3d.

Digital image analysis.png

$\bullet$ Geometric representation of scanned objects via triangular meshes:

Scanning and point cloud.png

In order to understand what is the right way to discretize the space, we will consider the approaches common in, as an example, digital image analysis.

Digital images: wire-frames or tiles?

An image is a grid of “pixels” marked in black and white (binary) or shades of gray (grayscale):

Balls pixelated.png

Now, how do you capture objects depicted in the images? These objects are made of pixels and, therefore, every pixel must be some kind of geometric object itself and not just a location. What are those elementary objects and how do they form objects?

One view is that pixels are dots. The dots are located at the nodes of a grid:

Pixel-dots.png

Next, to study the topology of the image one has to understand how these dots form objects. This requires the notion of adjacency among dots. One thinks of them as nodes of a graph and if two dots are adjacent, they are connected by an edge of the graph:

Pixel-dots edges.png

The result is a wire-frame which may be called a graph representation of the image.

This seems simple enough. However, the decision which nearby dots are adjacent isn't obvious. Should they be connected only along the grid? Or should the adjacency be recognized diagonally as well? These two approaches are called:

  • $4$-connectivity: each dot has $4$ neighbors, and
  • $8$-connectivity: each dot has $8$ neighbors.

At this point we realize that you can't choose $4$-connectivity over $8$-connectivity or vice versa as both are equally legitimate!

One may hope that choosing one of the two and sticking with it will provide a solid foundation for studying the topology of images. The trouble starts when one considers the complement of an object represented by dots. One would expect that the complement should also be an object represented by dots based on the same adjacency relation. Consider this picture however.

Pixel adjacency.png

If adjacency goes diagonally then $A$ and $D$ are connected to each other. Then $B$ and $C$ are not connected, so adjacency does not go diagonally. Wait a minute...

Exercise. Show that the Jordan theorem: the complement of a closed curve with no self-intersections in the plane has two connected components, fails in this setting. Hint: use the above analysis.

Things don't get any simpler as you move to higher dimensions:

3d grid.png

Exercise. List all possible ways to define adjacency in 3d.

We will take the Euclidean view instead:

the universe is a continuum.

We will break our continuous universe into small, discrete -- but still continuous! -- pieces.

Practically speaking:

We think of pixels as tiles. We think of voxels as bricks.
Tiles and bricks.png

This is how the object in the image above can be represented with tiles:

Tiles form an object.png

The Euclidean approach

Initially, our interest is to break the Euclidean space into pieces that are

  • 1. Euclidean,
  • 2. topologically “trivial”, and
  • 3. “small”.

Let's illustrate these terms with an example. We just take the grid on the plane and its decomposition into those little squares. In 3d, it's little cubes. Mathematically we represent the pieces as follows:

  • A pixel is a square $[n, n + 1] \times [m, m + 1]$ in the plane.
  • A voxel is a cube $[n, n + 1] \times [m, m + 1] \times [k, k + 1]$ in space.

Since these pieces are discrete, we can model and study the universe with computers. On the other hand, put together these “pixel-tiles” form a continuum. Both this continuum and each of these pieces can be studied with the tools accumulated over the last $2$ thousand years:

The idea of discretization of space can be traced back to Poincare who was studying the topology of manifolds around 1900 and had to devise a way of computing their topological properties: the number of path-components , the number of holes/tunnels , etc. His answer was to break these objects into elementary pieces, typically triangles. By mid-20th century, this theory, called algebraic topology, had reached a well-developed stage. In particular, it was proven that the algebraic results of this analysis are independent of your choice of discretization.

In fact, the shapes of these pieces may be arbitrary. They may be squares, triangles, hexagons, etc, as in a “tessellation”. The shapes may vary within the same decomposition, they may even be curved; the approach remains valid. Generally, these tiles, and bricks, are called cells.

Thus, the Euclidean space is cut into pieces and when these pieces are glued together, the original space reappears fully intact. From those pieces we form objects.

Let's consider this idea of discretization in a more general way. Even though we cut pieces from the Euclidean space, we might end up with subsets with “exotic” topology. For example, the closure of the graph of $y=\sin (1/x)$ has three path-components but two of them aren't closed! To avoid these abnormalities, it makes sense to consider open subsets of ${\bf R}^n$. The advantage is that every point has a neighborhood homeomorphic to ${\bf R}^n$. These pieces are indeed Euclidean.

Open, connected, non-empty subsets of ${\bf R}^n$ are called open regions. Their closures are called closed regions. For the latter, every point in their interior has a neighborhood homeomorphic to ${\bf R}^n$.

We also want these pieces to be topologically trivial: path-connected, no tunnels, no voids, etc. The idea is that the topological features of the objects formed by these pieces come from the way they are put together not from the topology of each piece.

These are a few possibilities...

$\bullet$ Square tessellation:

Grid-big.png

$\bullet$ Triangular tessellation:

Grid-Tri.jpg

$\bullet$ Hexagonal tessellation:

Grid-hexagon.jpg

What makes these regular discretization schemes small is the possibility of refinement. Refining these decompositions into ones with smaller and smaller cells allows us to approximate the space. Moreover, discrete functions defined on these discrete structures approximate continuous functions defined on the space:

Realizations of simplicial maps dim 1.png

Since, for now, we are prepared to forgo this requirement, we can choose cells of arbitrary shapes:

$\bullet$ Cell decomposition of plane:

Cell decomposition of plane.png

More building blocks

This isn't the end of the story. Some questions remain, such as: are lines also made of pixels? Without making sense of curves we can't study topology and path-connectedness in particular.

But curves made of pixels produce pictures like this:

Line from pixels.png

This “curve” isn't a curve in the usual topological sense! The reason is a curve should be $1$-dimensional as the image of the $1$-dimensional interval $[a,b]$.

The idea is, curves should be made of the edges of our tiles.

Then, a “discrete” -- but still Euclidean! -- curve will look like this:

Digital Euclidean curve.png

This idea isn't entirely new; just contrast the two images below:

Pixels and edges.png

Consider the complete cell decomposition of the pixel below and observe that the edges and vertices are shared with adjacent pixels:

Pixel decomposition.png

Meanwhile, a mismatch of the dimensions also appears in 3d if you try to use voxels to make surfaces. In fact, surfaces should be made of faces of our bricks. This is what a “discrete” surface looks like:

Digital surface.png

It's still a surface!

This idea necessitates augmenting the collection of $N$-dimensional cells in ${\bf R}^N$ with cells of lower dimensions.

The cell decomposition of the voxel follows and, once again, the faces, edges, and vertices are shared:

Voxel.png

To see the full picture, given a $2$-dimensional grid, we define (closed) cells for all integers $n,m$ as follows:

  • a vertex is $\{ n\} \times \{ m\}$;
  • an edge is $\{n \} \times [m, m + 1]$ or $[n, n + 1] \times \{m \}$;
  • a pixel is $[n, n + 1] \times [m, m + 1]$.
Cubical grid.png

One can interpret these literally as the building blocks for everything:

  • dimension $1$: sticks and wires;
  • dimension $2$: tiles and plywood boards;
  • dimension $3$: bricks and logs.

This is a uniform terminology for all dimensions:

  • a vertex is a $0$-cell,
  • an edge is a $1$-cell,
  • a pixel is a $2$-cell,
  • a voxel is a $3$-cell,
  • etc.

Now, we are on a solid ground to address adjacency. As the image is made of pixels, they are attached to each other along the edges they share. Again, this it is easily applicable to all dimensions, as follows.

Two adjacent edges, $1$-cells, share a vertex, $0$-cell:

Adjacency1.png

Two adjacent pixels, $2$-cells, share an edge, $1$-cell:

Adjacency2.png

Two adjacent voxels, $3$-cells, share a face, $2$-cell:

Adjacency3.png

The hierarchy becomes clear.

Thus, our approach to decomposition of space, in any dimension, boils down to the following:

The space is composed of cells in such a way that $k$-cells are attached to each other along $(k-1)$-cells.