A Property of Simple Voxels
by
T. Y. Kong
Queens College/CUNY

Define a voxel to be a closed unit cube [i, i+1] ×[j, j+1] ×[k, k+1] in Re³, where i, j and k are integers. For any voxel v, write Bd v to denote the boundary of v (i.e., the union of the six faces of v).

Let F be any set of voxels. Say that a voxel v in F is simple in F if both of the sets (Bd v) \cap \cup (F - {v}) and (Bd v) - \cup (F - {v}) are non-empty and connected. Say that a set of voxels X subset F is simple in F if X is finite and there exists an enumeration x₀, x₁, ... , x_k of X such that each voxel x_i is simple in F - {x_j | 0 <= j < i}. (In particular, \emptyset is simple in F, and a singleton subset {v} of F is simple in F if and only if the voxel v is simple in F.) This talk will discuss the following property of simple voxels:

Theorem. Let F be any set of voxels. Let X subset F and v in F - X be such that both X and X \cup {v} are simple in F. Then v is simple in F - X.

This result plays a significant role in the theory of 3-d parallel thinning algorithms. Such algorithms are used in digital image processing to reduce sets of voxels to ``skeletons''. Although the statement of the result does not involve any topological concept beyond connectedness, the author does not know of a proof which does not involve concepts that are unfamiliar to most computer scientists (such as the fundamental group, homology groups and homotopy equivalence).

Date received: April 12, 1996

Copyright © 1996 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caae-46.