Ghost

What a scanner cannot see

Two different pictures can give the same count on every beam. The difference between them, filled squares that become empty and empty ones that fill, is invisible to the scanner: in the tomography literature it is called a switching component, or a ghost. Each board below holds a pair of twins. Flip between them: no count moves.

Why another angle never gets rid of ghosts

Stretch a rubber band around the cells of any ghost. Now slide a beam along one side of the band until it just touches. It cannot touch a single cell, because one cell changing would change that beam's count. So it touches at least two, and the band has a straight side running in that beam's direction. That is true on both sides, for every direction the scanner uses.

So a ghost against two directions has a band with at least four sides, and at least four corners, every one of them a cell. Against three directions, at least six. Against four, at least eight. The boards above meet each bound exactly; the verifier searched every pattern on a 4×4 board, the size of these, and found nothing smaller. Adding an angle can never make the smallest ghost smaller (a ghost against more directions is still a ghost against fewer), and here each one makes it bigger. None makes ghosts impossible: on a large enough grid there is a ghost for any finite set of directions.

The two that fool all four beams

The last pair above are two little pinwheels, mirror images, eight cells each. Both are convex: each is exactly the set of grid points inside its own outline, no dents. That matters, because convex shapes are the easy case.

In 1997 R. J. Gardner and Peter Gritzmann proved that four well-chosen directions are enough to tell any two convex shapes on a grid apart, and that, in their words, “three X-rays do not suffice for this purpose.” Which four matters. Their guarantee covers “any set of four lattice directions whose slopes (suitably ordered) yield a cross ratio not equal to 4/3, 3/2, 2, 3 or 4.” Put this game’s four in order of angle (horizontal, one diagonal, vertical, the other diagonal) and the cross ratio of their slopes, 0, 1, infinity and −1, comes out at exactly 2. The guarantee does not reach these four, and the pinwheels show that uniqueness really fails for them: two convex shapes, the same count on every beam. Any seven directions, they also proved, always suffice.

Choosing each beam after you have seen the last one is a cousin of what the same paper calls “successive determination, in which the information from previous projections can be used in deciding the direction for the next projection”: there you choose the next direction, here the next single line. The subject has a practical root. The paper opens with a 1994 symposium on discrete tomography organized by Larry Shepp, whom a physicist had asked for help with electron-microscope images; a new technique could count the atoms on each line through a crystal, in certain directions. The numbers on the dots above are that kind of count.

Two directions are solved; three are hard

With rows and columns alone, deciding whether a picture exists and whether it is unique is old and settled. In 1957 H. J. Ryser proved that any two tables of 0s and 1s with the same row and column sums can be turned into each other “by a finite number of interchanges”, his name for the rectangle-corner swap on the first board above, and David Gale found, independently, the test for whether a table with given sums exists at all. Add a third direction and the problem changes character: Gardner, Gritzmann and Prangenberg showed in 1999 that deciding whether any picture fits a set of counts, and whether a second picture fits the same counts, takes polynomial time for two directions and is NP-complete for three or more. Your browser copes because the boards here are small, and every daily was checked in the lab before it was scheduled. Later writers gave the swaps many names; Brunetti, Dulio, Hajdu and Peri list “Switching components, also named as bad configurations, interchanges, and ghosts (according to different scenarios)”.

The grown-up version

A hospital CT scanner solves a continuous cousin of this game. Its rays “sweep in many directions through a cross-section”, each reports how strongly the X-rays were absorbed along its line rather than a whole-number count, and a computer rebuilds the slice “by solving a large number of equations including a corresponding number of unknowns”, as the 1979 Nobel press release put it. That year’s Prize in Physiology or Medicine went to Allan M. Cormack and Godfrey N. Hounsfield “for the development of computer assisted tomography”. For what a scanner loses when it cannot go all the way round a real object, see The Wedge the Scanner Never Saw.

Sources: R. J. Gardner and P. Gritzmann, “Discrete tomography: determination of finite sets by X-rays”, Trans. Amer. Math. Soc. 349 (1997) 2271–2295 (Theorems 4.5, 5.5 and 5.7). H. J. Ryser, “Combinatorial properties of matrices of zeros and ones”, Canad. J. Math. 9 (1957) 371–377 (Theorem 3.1). D. Gale, “A theorem on flows in networks”, Pacific J. Math. 7 (1957) 1073–1082. R. J. Gardner, P. Gritzmann and D. Prangenberg, “On the computational complexity of reconstructing lattice sets from their X-rays”, Discrete Math. 202 (1999) 45–71, as stated in A. Alpers and P. Gritzmann’s 2018 survey (arXiv:1809.06141, Theorem 13). S. Brunetti, P. Dulio, L. Hajdu and C. Peri, “Ghosts in Discrete Tomography”, J. Math. Imaging Vis. 53 (2015) 210–224. NobelPrize.org, the 1979 Physiology or Medicine summary and press release.