On the reconstruction of planar lattice-convex sets from the covariogram

Abstract

A finite subset $K$ of ${\mathbb{Z}}^d$ is said to be lattice-convex if $K$ is the intersection of ${\mathbb{Z}}^d$ with a convex set. The covariogram $g_K$ of $K\subseteq {\mathbb{Z}}^d$ is the function associating to each $u \in \integer^d$ the cardinality of $K\cap (K+u)$. Daurat, Gérard, and Nivat and independently Gardner, Gronchi, and Zong raised the problem on the reconstruction of lattice-convex sets $K$ from $g_K$. We provide a partial positive answer to this problem by showing that for $d=2$ and under mild extra assumptions, $g_K$ determines $K$ up to translations and reflections. As a complement to the theorem on reconstruction we also extend the known counterexamples (i.e., planar lattice-convex sets which are not reconstructible, up to translations and reflections) to an infinite family of counterexamples.

accepted in Discrete and Computational Geometry

References in corpus (5)

• Homometric model sets and window covariograms
• The covariogram determines three-dimensional convex polytopes
• Phase retrieval for characteristic functions of convex bodies and reconstruction from covariograms
• Covariogram of non-convex sets
• The cross covariogram of a pair of polygons determines both polygons, with a few exceptions

Cited by in corpus (1)

• Homometry and direct-sum decompositions of lattice-convex sets