On a reconstruction problem of Harary and Manvel (Q1865368)

This paper is on the reconstruction of finite sets of points in the plane \(\mathbb{R}^2\). Two sets of points in the plane are considered isomorphic if one can be transformed into the other by a suitable translation and/or a rotation by a multiple of \(90^\circ\). The main result of this paper can be stated as follows. Let \(A,B\subseteq\mathbb{R}^2\) be two non-isomorphic finite sets and let \(\{a_1,\dots, a_n\}\subseteq A\) and \(\{b_1,\dots,b_n\}\subseteq B\) be such that \(A-\{a_i\}\approx B-\{b_i\}\) for \(1\leq i\leq n\). Then \(n\leq 4\). The author provides an example to show that this result is best possible. This result settles a combinatorial reconstruction problem posed by \textit{F. Harary} and \textit{B. Manvel} [Bull. Soc. Math. Belg. 24, 375-379 (1972; Zbl 0279.05128)]. The problem was to determine the reconstruction number for square-celled animals. A square-celled animal is a finite set of rookwise-connected squares in the plane that form a simply connected region, and a subanimal arises from an animal by deleting one square. Animals are considered isomorphic if one can be transformed into the other by translation and/or rotation. The reconstruction number of square-celled animals is the minimum number of subanimals (given up to isomorphism) that uniquely determine any square-celled animal up to isomorphism. Since there is a natural correspondence between square-celled animals and certain sets of points in the plane, the result proved in this paper implies that the reconstruction number for square-celled animals is 5.