On the Reconstruction of Planar Lattice-Convex Sets from the Covariogram

Gennadiy Averkov, Barbara LangfeldDiscret. Comput. Geom 2012 · OpenReview

TL;DR

This paper tackles the problem of reconstructing planar lattice-convex sets (essentially, discrete sets that can be formed by intersecting a convex shape with a grid) from their "covariogram," which is a measure of how much the set overlaps with its shifted copies. The authors provide a significant positive result: under certain mild conditions, the covariogram uniquely determines the set up to translation and reflection. They also contribute to understanding the limitations by constructing an infinite family of sets that cannot be uniquely determined.

What Problem Does This Paper Address?

The core problem is a discrete version of a classic question in geometric tomography: can we uniquely identify a shape if we only know how much it overlaps with its shifted versions? Specifically, the paper focuses on "lattice-convex sets" in 2D. These are sets of points on a grid (like ℤ²) that can be formed by taking a standard convex shape (like a polygon) and keeping only the grid points inside it. The "covariogram" of such a set $K$, denoted $g_K$, is a function that, for every grid vector $u$, tells us the number of points in $K$ that are also in $K+u$ (where $K+u$ is the set $K$ shifted by $u$).

The problem, raised by researchers like Daurat, Gérard, Nivat, Gardner, Gronchi, and Zong, is whether knowing $g_K$ is enough to recover $K$. Since shapes can be shifted and reflected without changing their covariogram, the goal is to determine $K$ "up to translations and reflections." While previous work has shown that this is not always possible, this paper aims to provide a more complete picture by identifying conditions under which reconstruction is possible and by characterizing the cases where it is not.

Methods

The paper employs a combination of geometric and combinatorial techniques. A key approach is to relate the covariogram $g_K$ to the "local boundary information" of the lattice-convex set $K$. This includes identifying the directions of the edges of $K$ and the number of lattice points on these edges. The authors leverage discrete analogues of arguments used in the continuous version of the covariogram problem, adapting them to the grid setting.

They introduce several quantitative measures to characterize the set $K$ and its covariogram:

  • $m'(K)$ and $m''(K)$: measures related to the number of lattice points on edges and differences in lengths of parallel edges.
  • $m(K)$: a combined measure of the above.
  • $U(K)$: the set of primitive normal vectors to the edges of $K$.
  • $\delta(K)$: a "discrepancy" measure related to the density of lattice points within cones formed by edge directions.

The positive result (Theorem 2.1) relies on showing that if these measures satisfy certain inequalities (specifically, $m(K)$ is sufficiently large compared to $\delta(K)$), then $K$ is uniquely determined up to translations and reflections. The proof involves intricate arguments about how the covariogram encodes geometric properties and how these properties can be "glued" together to reconstruct the set.

For the negative results, the authors construct an infinite family of counterexamples. These are based on the concept of "direct sums" of lattice sets ($S \oplus T$), where $S$ and $T$ are lattice sets such that their Minkowski sum $S+T$ has a specific structure. They show that certain pairs of sets formed this way ($S \oplus T$ and $S \oplus (-T)$) can have the same covariogram but are not translations or reflections of each other, especially when $S$ and $T$ are not centrally symmetric.

Datasets

Not discussed in the paper. The paper deals with theoretical reconstruction problems for abstract sets, not empirical data analysis.

Key Insights and Ideas

  • Covariogram as Boundary Information: The covariogram $g_K$ is not just a measure of overlap; it implicitly encodes crucial information about the boundary of the lattice-convex set $K$, particularly its edges and their orientations.
  • Quantitative Conditions for Uniqueness: The paper establishes that specific quantitative properties of the set's edges and their directions (captured by $m(K)$ and $\delta(K)$) are critical for unique reconstruction. If these measures are "large enough," reconstruction is guaranteed.
  • The Role of "Discrepancy": The measure $\delta(K)$ quantifies the "unbalancedness" of the lattice point distribution within the cones formed by edge directions. A high discrepancy suggests a more complex or less symmetric structure, which can lead to non-uniqueness.
  • Direct Sums and Homometry: The construction of counterexamples relies heavily on the concept of direct Minkowski sums ($S \oplus T$). Pairs of sets of the form $S \oplus T$ and $S \oplus (-T)$ can be "homometric" (having the same covariogram) if $S$ and $T$ are not centrally symmetric, providing a systematic way to generate non-reconstructible cases.
  • Discrete vs. Continuous: The paper highlights how discrete structures introduce nuances not present in the continuous covariogram problem, particularly when edge lengths differ or when sets are not centrally symmetric.

Key Results

  • Theorem 2.1 (Positive Result): For a planar lattice-convex set $K$, if its covariogram $g_K$ satisfies certain conditions (related to $m(K)$ and $\delta(K)$ being sufficiently large), then $K$ is uniquely determined up to translations and reflections. This provides a significant positive answer to a long-standing problem.
  • Infinite Family of Counterexamples: The paper constructs an infinite family of planar lattice-convex sets that are not uniquely determined by their covariograms. These are derived from direct sums of lattice sets and are characterized by specific geometric properties (e.g., $T$ having lattice width 1).
  • Characterization of Non-Reconstructible Sets: Theorem 2.5 provides a characterization of a specific class of non-reconstructible sets, linking them to direct sums of a lattice set $S$ and a set $T$ with lattice width 1.

Limitations and Future Work

  • Dimensionality: The paper focuses on $d=2$. The authors note that generalizing Theorem 2.1 to higher dimensions ($d \ge 4$) is a nontrivial task and may require fundamentally different approaches, as constructions for higher dimensions can lead to a vast class of non-reconstructible sets.
  • Complete Classification: While the paper provides a partial positive result and characterizes a family of counterexamples, a complete classification of all planar lattice-convex sets that are uniquely determined by their covariograms remains an open question.
  • Algorithmic Reconstruction: The proof of Theorem 2.1 suggests that the reconstruction process could be made algorithmic under the given conditions, but a detailed analysis of algorithmic issues is beyond the scope of this paper.
  • Geometrically Constructible Homometric Pairs: The paper poses the question of whether there exist homometric pairs of lattice-convex sets that are not geometrically constructible (i.e., not formed by direct sums of the type $S \oplus T$ and $S \oplus (-T)$). Their computer search suggests that for small sets, all homometric pairs are geometrically constructible.

Summary updated

Abstract

A finite subset K of ℤd is said to be lattice-convex if K is the intersection of ℤd with a convex set. The covariogram g K of K⊆ℤd is the function associating to each u∈ℤd the cardinality of K∩(K+u). Daurat, Gérard, and Nivat and independently Gardner, Gronchi, and Zong raised the problem of 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.
BibTeX
@inproceedings{averkov2012reconstruction,
  author = {Gennadiy Averkov and Barbara Langfeld},
  title = {{On the Reconstruction of Planar Lattice-Convex Sets from the Covariogram}},
  booktitle = {Discret. Comput. Geom},
  year = {2012},
  url = {https://openreview.net/forum?id=GE0RRchNXs},
}
Figure