Reconstructing polygons from X-rays (Q1919271)

The paper contains results on the geometric tomography of polygons in the plane. The authors present strategies for the interactive reconstruction of simple polygons from carefully chosen \(X\)-ray probes, thus generalizing previous results about convex polygons. In particular, they show that \(n+h+2\) parallel \(X\)-ray probes suffice to determine an \(n\)-gon \(P\) with \(h\) vertices on its convex hull (no three vertices being collinear). Furthermore, if an upper bound \(n'\) on the number of vertices of \(P\) is given, then \(2n'+2\) parallel probes or \(3n'\) origin probes are sufficient. Recently, R. Gardner proved that star-shaped polygons cannot be reconstructed from a constant number of parallel \(X\)-ray probes from predetermined directions. Here a logarithmic lower bound for the much stronger case of interactive reconstruction is proved, although the considered polygons are not necessarily star-shaped. In the final part of the paper, some interesting open questions are collected (referring to simple polygons with holes, to non-simple polygons and to higher dimensions, etc.).