covariograms

The covariogram of a set A in Euclidean space is a function that measures how much A overlaps with a translate of itself. For a measurable set A in R^n with finite Lebesgue measure, the covariogram g_A is defined by g_A(h) = vol(A ∩ (A + h)) for vectors h in R^n. In digital images, a discrete version uses counting measure. The covariogram captures the two-point overlap structure of A.

Key properties include that g_A is nonnegative and symmetric: g_A(h) = g_A(-h). The value at the origin is the volume of A, g_A(0) = vol(A). The support of g_A is contained in A − A, the Minkowski difference, since A ∩ (A + h) is nonempty only when h lies in that set. If A is bounded, g_A is continuous; smoother boundaries often yield additional regularity.

The covariogram problem, first posed by Matheron, asks to what extent A can be reconstructed from g_A. In general, uniqueness fails for some sets, but for many classes of bodies—especially convex bodies in low dimensions—g_A determines A up to translation and reflection (with certain exceptions). The problem connects geometry with statistical descriptions of sets and has driven a range of theoretical and applied results.

Applications appear in stochastic geometry, image analysis, and materials science as a two-point correlation or texture descriptor. In random media, the covariogram generalizes to the probability that a stationary random set intersects itself after a shift, serving as a practical tool for characterizing spatial structure and for tasks such as reconstruction, segmentation, and texture analysis.