ON WHICH GRIDS CAN TOMOGRAPHIC EQUIVALENCE OF BINARY PICTURES BE CHARACTERIZED IN TERMS OF ELEMENTARY SWITCHING OPERATIONS

It is a well-known result, due to Ryser, that if a binary picture on t he square grid has the same x and y projections as another such pictur e, then the first picture can be transformed into the second by a seri es of switching operations, each of which changes the picture at just four grid points and preserves both projections. In this article, we s how that if a grid [such as a two-dimensional (2D) hexagonal grid or t he 3D cubic grid] has three or more directions of projection, then Rys er's result has no analog for that grid. Specifically, we show that on any grid with three or more directions of projection there cannot exi st any constant L such that every binary picture can be transformed to any other binary picture with the same projections by a series of pro jection-preserving changes, each of which involves at most L grid poin ts. This is proved for a very general concept of ''grid'' that encompa sses virtually all practical grids in Euclidean n-space, and even some grids in higher-dimensional analogs of cylindrical and toroidal surfa ces. (In fact, the set of grid points can be any finitely generated Ab elian group of rank greater than or equal to 2.) (C) 1998 John Wiley & Sons, Inc.