Chapter 3 Tomographic Equivalence and Switching Operations
T. Yung Kong, Gábor T. Herman · 1999
A binary picture on an arbitrary grid is a mapping f from the set of all grid points to {O,I} such that f(x)=1 for only finitely many grid points x. If two binary pictures hand /2 on the same grid have the property that for every grid lineR the sets {pEf. I h (P)=I} and {pE f. I /2 (P)=I} contain exactly the same number of grid points, then we say that hand /2 are tomographically equivalent. Given a binary picture f on the usual 2-dimensional square grid, there may exist an upright rectangle R (of any size) whose sides are grid lines, such that f= 1 at two diagonally opposite comer points of Rand f= 0 at the other two comer points. If so, then we call the process of changing the value of the picture f from 1 to 0 and 0 to 1 at the four comer points of R (without changing the value of f at any other grid point) a rectangular 4-switch. Ryser showed in the 1950s that two binary pictures on the square grid are tomographically equivalent if and only if one picture can be transformed to the other by a finite sequence of rectangular 4-switches. We present a few different versions of this theorem, describe an application, and also give a proof of the result. We then show that the result has no analog on grids that have grid lines in three or more directions (such as the 3-dimensional cubic grid), because on such grids one can find for every integer L two tomographically equivalent binary pictures that differ at more than L grid points and are not tomographically equivalent to any other binary picture.