j. differential geometry 60 (2002) 177-198

THE SOLUTION OF THE COVARIOGRAM PROBLEM FOR PLANE C_{+}^{2} CONVEX BODIES

GABRIELE BIANCHI, FAUSTO SEGALA & ALJOŠA VOLČIČ

Abstract

We prove that the geometric covariogram determines (up to translation and reflection), among all convex bodies, any plane convex body which is C^{2} and has positive curvature everywhere. This gives a partial answer to a problem posed by G. Matheron.

1. Position of the problem

A convex body in ℝ^{m} is a compact convex set K with non empty interior. We say that a convex body is of class C_{+}^{2} if ∂K, the boundary of K, is a C^{2} (m − 1)-dimensional submanifold of ℝ^{m} and if its Gauss curvature is positive at every z ∈ ∂K.

By S^{m−1} we denote the unit m-sphere, i.e., the set of all vectors u ∈ ℝ^{m} such that ∥u∥ = 1.

The width function of a convex body K in direction u is the distance between the planes supporting K orthogonal to u, and is denoted by w_{K}(u).

A convex body K ⊂ ℝ^{m}, belonging to the class C_{+}^{2}, is strictly convex, therefore the point z_{u} ∈ ∂K where the outward normal is u, is uniquely determined for each u ∈ S^{m−1}.

By τ_{K}(u) we will denote the Gauss curvature of ∂K at z_{u}.

We will denote by λ_{m} the m-dimensional Lebesgue measure on ℝ^{m}. If x ∈ ℝ^{m}, K + x denotes the translate of K by x, i.e.,

K + x = {z : z ∈ ℝ^{m}, z = x + y, y ∈ K}.

Received August 23, 2001.

If K ⊂ ℝ^{m} is a convex body, then its (geometric) covariogram g_{K}(x) is the function defined for x ∈ ℝ^{m} by

g_{K}(x) = λ_{m}(K ∩ (K + x)).

G. Matheron investigated in [24] the covariogram function and posed in [25] the following question.

Covariogram Problem. Does the geometric covariogram determine a convex body K in ℝ^{m}, among all convex bodies, up to translation and reflection?

Reflection in this paper always means reflection at a point.

W. Nagel [30] gave a first partial answer to the problem confirming the conjecture for the class of plane convex polygons.

The problem is related to other chord-length distributions and we refer to [26], [27] and [30] for an account on them and to related bibliography. In the update of the book [9], which can be reached at http://www.ac.wwu.edu/˜ gardner, there is a reference to the covariogram problem, and more about it can be found in [13].

The problem is posed here in purely geometric terms. It is worthwhile to note that Nagel’s paper basically uses geometric ideas, and that also this paper presents a proof based on geometric tools. As such the problem belongs to integral geometry and geometric tomography, but it is interesting to note that it is a special case of a widely studied problem in Fourier analysis, and also that an important step in our proof (see Section 3) can be achieved by Fourier analysis methods, as an alternative to a geometric method developed in Section 2.

The covariogram function can be in fact defined more generally for any real valued square integrable function f defined on ℝ^{m}, by

g_{f}(x) = ∫_{ℝ^{m}} f(t)f(t − x) dλ_{m}(t),

and therefore g_{f}(x) = (f ∗ f_{−})(x), where f_{−}(x) = f(−x). Taking the Fourier transforms, it turns out that

ĝ_{f}(ξ) = f̂(ξ)f̂_{−}(ξ) = f̂(ξ)\overline{f̂(ξ)} = |f̂(ξ)|^{2}.

When f = χ_{K} is the indicator function of K, g_{f} = g_{K}.

The more general problem of the determination of the function f, or of some of its features, from the modulus of its Fourier transform, has a vast literature. In this context, the reconstruction of f is called phase retrieval problem and has attracted the attention of many authors in various fields of mathematics (Fourier analysis [18], numerical analysis [1], probability [28], [5], [6]) and in the applications. A general reference is [17].

As it will be shown in Section 3, methods of Fourier analysis are actually relevant in solving the covariogram problem, since an appropriate asymptotic formula provides information about curvature, for strictly convex and sufficiently smooth convex bodies, at points of the boundary where supporting lines have opposite normals. The formula has been obtained first for the planar case in [16], and then extended to ℝ^{m} in [15]. The papers [20] and [14] are also standard references. For recent and more general results concerning nonsmooth or nonconvex domains, see [31] and [4].

Phase retrieval has important applications in optics and optical design, quantum mechanics (Pauli uniqueness problem), radar ambiguity problem, astronomy, light and electron microscopy, X-ray crystallography, wave-front sensing, pupil-function determination and particle scattering (see for instance [19], [32], [38]). Since the solution of the phase retrieval problem is highly nonunique (even apart from the already mentioned translation and reflection), and ill-posed, one usually assumes some additional condition or a priori information on the function to be reconstructed (see [37], [3], [7], [8]). Matheron’s problem can also be seen from this point of view.

Some aspects of the phase retrieval problem are of combinatorial nature. Two finite multisets (sets with repetitions allowed) A and B in ℝ^{n} are said to be homometric if the sets of the vector differences {x − y : x, y ∈ A} and {x − y : x, y ∈ B} are identical, counting multiplicities. The problem consists in determining all the multisets which are homometric to a given multiset. The paper [33] is devoted to this question and gives also some examples of sets of integers (not multisets) which are not uniquely determined by their vector differences. From these examples one can easily construct sets of positive measure on the real line or in ℝ^{m} which are not uniquely determined by their covariogram function. Since the sets A = {0, 1, 3, 8, 9, 11, 12, 13, 15} and B = {0, 1, 3, 4, 5, 7, 12, 13, 15} are homometric, a cover of A and B by a union of intervals of length δ < \frac{1}{2}, centered at the points of A and B, respectively, produces two sets of real numbers, A′ and B′, which are not translates or reflections of each other, but have the same covariogram.

The sets A′ × [0, 1]^{m−1} and B′ × [0, 1]^{m−1} are now two subsets of ℝ^{m}, which are not translations or reflections of each other, but have the same covariogram.

The paper [23] provides a general algebraic approach to the generation of homometric sets. That paper is also the first to mention the method described above, which permits one to construct, from finite homometric sets, sets of positive measure on the real line with the same covariogram, which are not reflections or translations of each other.

Homometric sets have applications in beam manipulation [2].

An entirely different planar example of nonuniqueness has been found by R. Gardner and P. Gronchi (private communication). It is obtained as connected union of fifteen adjacent lattice squares such that every line parallel to one of the sides intersects the set in a segment.

As we have already mentioned, the covariogram identifies (up to translation and reflection) a set A or a density f only in special cases (within a restricted class, or with additional information). Therefore the covariogram is often used as a tool for “disentangling different structures imbricated within each other” [35]. The covariogram can be used for example to describe structures with distinct size distributions, to identify superposition of scales, to analyse clusters of particles, to identify periodicities or pseudo-periodicities, noise due to technology, multiphased structures, “rose of directions” and anisotropies. Moreover, the covariogram can be used to estimate the variance of samplings. For more information, see the rich literature quoted in [35] and the papers [36] and [21].

We will give in this paper another partial positive answer to Matheron’s question, proving the following theorem:

Theorem 1.1. If K is a plane convex body in C_{+}^{2}, then its geometric covariogram determines K among all convex bodies up to translation and reflection.

The plan of the proof is the following.

Sections 2 and 3 provide two different methods for proving that the covariogram function of a C_{+}^{2} convex body determines the (nonordered) pair of curvatures {τ(u), τ(−u)} for all u ∈ S^{1}. The first method is direct (and allows possible extensions to classes of other planar convex bodies), while the other method uses a Fourier transform approach and admits extensions to higher dimensions.

In the short discussion at the beginning of Section 4 we will describe how this result allows one to determine uniquely, up to translation and reflection, certain opposite arcs of ∂K.

A geometric argument (Lemma 4.2) and a little bit of analysis (Proposition 4.3) will then show, under the assumption that K ∈ C_{+}^{2}, that there is just one way of gluing together these arcs and that their union gives all of ∂K.

In Section 5 we shall prove that the covariogram of a convex body in C_{+}^{2} determines the C_{+}^{2} regularity of the body and therefore that a body K ∈ C_{+}^{2} is uniquely determined by its covariogram function among all convex bodies.

In the last section we shall show that most convex bodies in ℝ^{m} are uniquely determined (up to reflection and translation) by their covariogram function. For m ≥ 3, this follows from a result by Goodey, Schneider and Weil [12], while our result covers the case m = 2. For m=1 much more is known, namely that any bounded interval is determined up to translation by its covariogram function.

The first author was the first to obtain the results from Sections 2 and 4 (with proofs that differ from those which are presented in this paper). Section 3 is due to the second author. The third author worked out independently Sections 2 and 4. At this point the cooperation between the three authors produced Sections 5 and 6. Section 5 is mainly due to the first author, while Section 6 is mainly due to the third author.

The authors are indebted with Richard Gardner, who introduced them to the covariogram problem and had with them many stimulating discussions.

Very shortly before the submission of this paper, the first author has been able to construct pairs of convex bodies in ℝ^{n}, for any n ≥ 4, which have the same covariogram and which are not a translation or a reflection of each other. This result will appear elsewhere.

2. Local determination of the curvature

From now on, all the convex bodies will be planar, except otherwise stated. The next lemma determines locally, up to reflection, the curvature of ∂K from the covariogram function.

Lemma 2.1. If K ∈ C_{+}^{2} then the covariogram function of K determines the (nonordered pair) {τ_{K}(u), τ_{K}(−u)} of curvatures at the points z_{u} and z_{−u}.

Proof. Changing, if necessary, the coordinate system, we may assume that z_{u} is the origin and that the line supporting K at z_{u} is the x-axis and that K is contained in the half-plane {(x, y) : y ≤ 0}.

Since K is sufficiently smooth, ∂K can be approximated (up to terms of higher order) by the graph of the parabola y = −βx^{2} for some positive β. Let (z_{1}, z_{2}) be the coordinates of z_{−u} in the new coordinate system. The bodies K and K − z_{−u} intersect at the origin. Let us approximate, up to terms of higher order, the part of ∂K − z_{−u} containing the origin by the parabola y = αx^{2}, for some positive α.

For t > 0 and s sufficiently small, K ∩ (K + (−z_{1} + s, −z_{2} − t)) is contained in a set

{(x, y) : α_{2}(s, t)(x − s)^{2} − t ≤ y ≤ −β_{2}(s, t)x^{2}}

and contains a set

{(x, y) : α_{1}(s, t)(x − s)^{2} − t ≤ y ≤ −β_{1}(s, t)x^{2}} ,

where 0 < α_{1}(s, t) < α < α_{2}(s, t) and 0 < β_{1}(s, t) < β < β_{2}(s, t), with

lim_{s→0 ,t→0^{+}} α_{i}(s, t) = α

and

lim_{s→0 ,t→0^{+}} β_{i}(s, t) = β,

for i = 1, 2.

A simple calculation shows that the area of the two sets is

\frac{4}{3} \frac{1}{(α_{i}(s, t) + β_{i}(s, t))^{2}} ((α_{i}(s, t) + β_{i}(s, t))t − α_{i}(s, t)β_{i}(s, t)s^{2})^{\frac{3}{2}} ,

for i = 1, 2, and therefore

(1) g_{K}((−z_{1} + s, −z_{2} − t))

= (\frac{4}{3} \frac{1}{(α + β)^{2}} ((α + β)t − αβs^{2})^{\frac{3}{2}} ) (1 + ϵ(s, t)),

with lim_{s→0 ,t→0^{+}} ϵ(s, t) = 0.

Letting s = 0, we get

g_{K}((−z_{1}, −z_{2} + t)) = \frac{4}{3} \frac{t^{\frac{3}{2}}}{\sqrt{α + β}} (1 + ϵ(0, t))

and this permits to evaluate α + β. Combining this with (1), we can also evaluate α · β, and therefore the pair {α, β}.

Since the pair of curvatures {τ_{K}(u), τ_{K}(−u)} of ∂K at z_{u} and z_{−u} is {2α, 2β}, Lemma 2.1 is proved. q.e.d.

Remark 2.2.

a) An alternative proof of Lemma 2.1 could be obtained from the observation that the radius of curvature R_{S}(u) of the support S of g_{K} at the point with outer normal u is the sum of the radii R_{K}(u) and R_{K}(−u) of K at z_{u} and z_{−u} and from the formula

g_{K}(z_{u} − z_{−u} − tu)

= 4/3\sqrt{2R_{K}(u)R_{K}(−u)/(R_{K}(u) + R_{K}(−u))} t^{3/2} + o(t^{3/2}).

The claim regarding R_{S}(u) is a consequence of the fact that S coincides with K + (−K) = {z = x − y : x, y ∈ K}.

b) With a technique similar to the one used in Lemma 2.1 we can find for planar C_{+}^{2} bodies the directional Taylor expansion of the covariogram function for small displacements, which may be of independent interest.

If u ∈ S^{1}, let us denote by u^{⊥} the line orthogonal to u through the origin. Then we have (with the usual notation)

g_{K}(tu) = λ_{2}(K) − t · w_{K}(u^{⊥}) + \frac{t^{3}}{24} (\frac{1}{τ(u)} + \frac{1}{τ(−u)} + η(t)) ,

with lim_{t→0} η(t) = 0.

3. The curvature in terms of the Fourier transform

Let us introduce the distribution χ_{∂K} defined by

(2) χ_{∂K}(ϕ) = ∫_{∂K} ϕ(x)(dx_{1} + i dx_{2}), x = (x_{1}, x_{2}), ϕ ∈ C_{0}^{∞}(ℝ^{2}).

From the point of view of the distributions, we have

χ̂_{∂K}(ϕ) = χ_{∂K}(ϕ̂) = ∫_{∂K} ϕ̂(x)(dx_{1} + i dx_{2})
= ∫_{ℝ^{2}} ϕ(ξ) dξ ∫_{∂K} e^{−i⟨x,ξ⟩}(dx_{1} + i dx_{2}),

where ξ = (ξ_{1}, ξ_{2}). Therefore the Fourier transform of the distribution χ_{∂K} is given by the analytic function

(3)  χ̂_{∂K}(ξ) = ∫_{∂K} e^{−i⟨x,ξ⟩}(dx_{1} + i dx_{2}).

An application of the divergence theorem gives

(4) ∫_{∂K} e^{−i⟨x,ξ⟩}(dx_{1} + idx_{2}) = ∫_{K} (i\frac{∂}{∂x_{1}} − \frac{∂}{∂x_{2}} ) e^{−i⟨x,ξ⟩} dx_{1} dx_{2}

and therefore

(5)  χ̂_{∂K}(ξ) = (ξ_{1} + i ξ_{2})χ̂_{K}(ξ).

The method of the stationary phase allows us to know the asymptotic behaviour of the integral in (3) as |ξ| → ∞. We recall that the asymptotic analysis of the Fourier transforms related to convex sets originated with Haviland and Wintner [16] (see also [20], [15], [14] and [31]).

In the next two statements we put u = ξ/|ξ|.

Lemma 3.1. Let K be a plane convex body whose boundary is C^{4} and has positive curvature everywhere. Then, as |ξ| → ∞,

(6) χ̂_{∂K}(ξ) = \sqrt{\frac{2π}{|ξ|}} σ^{∗}(u) (\frac{1}{\sqrt{τ_{K}(u)}}e^{iπ/4}e^{−i⟨z_{u},ξ⟩}

−\frac{1}{\sqrt{τ_{K}(−u)}}e^{−iπ/4}e^{−i⟨z_{−u},ξ⟩} + O (\frac{1}{\sqrt{|ξ|}})) ,

where σ^{∗}(u) = (−ξ_{2} + i ξ_{1})/|ξ|.

The proof of this result under these regularity assumptions is given in [14].

Since

(7)  ĝ_{K}(ξ) = |χ̂_{K}(ξ)|^{2},

from (5) and (7) we deduce that

(8)  ĝ_{K}(ξ) = \frac{1}{|ξ|^{2}} |χ̂_{∂K}(ξ)|^{2}.

The next result follows from Lemma 3.1 and (8).

Proposition 3.2. Let K be a plane convex body whose boundary is C^{4} and has positive curvature everywhere. Then, as |ξ| → ∞, the function ĝ_{K} admits the following asymptotic expansion

(9) ĝ_{K}(ξ) = \frac{2π}{|ξ|^{3}} (\frac{1}{τ_{K}(u)} + \frac{1}{τ_{K}(−u)}

−\frac{2}{\sqrt{τ_{K}(u) τ_{K}(−u)}} sin (|ξ|w_{K}(u)) + O (\frac{1}{\sqrt{|ξ|}})) .

As a consequence of formula (9), the knowledge of the function g_{K} (and hence its Fourier transform ĝ_{K}) implies the knowledge of the set {τ_{K}(u), τ_{K}(−u)}. This can be proved as follows. Let

(10)  ξ′_{k} = \frac{2πk}{w_{K}(u)}, ξ′′_{k} = \frac{(4k + 1)π}{2w_{K}(u)} .

From (10) we obtain

\frac{1}{τ_{K}(u)} + \frac{1}{τ_{K}(−u)} = \frac{1}{2π} lim_{k} |ξ′_{k}|^{3}ĝ_{K}(ξ′_{k})

and

\frac{1}{\sqrt{τ_{K}(u) τ_{K}(−u)}} = \frac{1}{2τ_{K}(u)} + \frac{1}{2τ_{K}(−u)} − \frac{1}{4π} lim_{k} |ξ′′_{k}|^{3}ĝ_{K}(ξ′′_{k}),

and obviously the last two equations determine {τ_{K}(u), τ_{K}(−u)}.

Remark 3.3. When K ∈ C_{+}^{2}, an extension of Lemma 3.1 proved by Podkorytov [31] under the sole assumption of convexity implies that the asymptotic expansion of ĝ_{K} determines the set {τ_{K}(u), τ_{K}(−u)} for almost any u ∈ S^{1}. The continuity of the curvature implies then that this set is determined for all u.

4. Determination of opposite arcs

Sections 2 and 3 only determine the nonordered pair of curvatures {τ_{K}(u), τ_{K}(−u)} for every u ∈ S^{1}, since a reflection does not change the covariogram function. Therefore these results are just a first step in the desired direction, but more is needed. Of course, if τ_{K}(u) = τ_{K}(−u) for all u ∈ S^{1}, then K is centrally symmetric and it is determined by the knowledge of K + (−K), the support of g_{K}, which in the case of symmetry coincides with 2K.

Suppose now that τ_{K}(u) ≠ τ_{K}(−u) for some u ∈ S^{1}. The invariance under translation allows us to fix for z_{u} ∈ ∂K an arbitrary point in ℝ^{2}. The covariogram function determines z_{−u}. Up to reflection we may assume that ∂K has curvature τ_{K}(u) at z_{u}. Then, by continuity of the curvature, there is a whole maximal open arc of S^{1} containing u, such that the curvatures at z_{v} and z_{−v} are different for all the points v of that arc, and by continuity it is determined by the choice of the curvature at z_{u}. At the endpoints of this arc there may be (on one side or on both sides) an adjacent arc on which the curvatures at z_{v} and z_{−v} coincide. By continuity of the curvature however, we have to reach finally two points v_{1} and v_{2}, determining an arc U, where the curvatures bifurcate, i.e., on each arc adjacent to U, there are points v such that the curvature at z_{v} differs from the curvature at z_{−v}. The knowledge of the curvatures uniquely determines the arcs of ∂K corresponding to U and −U via the parametric representation (see for instance [11], p. 79)

x(v) = x(u) + ∫_{θ(u)}^{θ(v)} \frac{− sin t}{τ_{K}(cos t, sin t)} dt,

y(v) = y(u) + ∫_{θ(u)}^{θ(v)} \frac{cos t}{τ_{K}(cos t, sin t)} dt,

where θ(v) denotes the angular coordinate of v ∈ S^{1}.

This is how far we can get with the results from Sections 2 and 3. It remains to prove that there is just one way of gluing together the opposite arcs of ∂K determined in that manner.

This, by the way, is a problem very similar to the one faced by Nagel in his paper dealing with convex polygons. Once he was able to prove that the covariogram function determines the length of all the edges, and — up to the sign — the corresponding outer normals, he refers to an “exhaustive case study” carried out in a previous paper [29], where he proved that the covariogram function provides all the information needed to assemble the edges, up to translation and reflection, in one way only.

Let us denote by A and B the arcs of ∂K corresponding to U and −U respectively, obtained as above. Suppose that there are two distinct convex bodies K and H having A and B in common and let us denote by A′ and B′ the connected components of ∂K ∩ ∂H containing A and B, respectively. It follows from the discussion above that A′ and B′ are not reflections of each other, that K and H have the same tangents at the endpoints of A′ and B′, and that these tangents are pairwise parallel. Moreover the subinterval of S^{1} which consists of the outer normals of A′ has length less than π and thus A′ can be represented as the graph of a convex function.

We will prove our claim if we show that A′ (and hence B′) is not maximal, that is ∂K ∩ ∂H contains an arc which is strictly larger than A′.

We now have to introduce a definition.

Definition 4.1. Suppose A′ and B′ are two arcs of ∂K corresponding to two opposite arcs U′ and −U′ of S^{1}, with K strictly convex. Let z be one of the endpoints of B′. Let us denote by B′ the convex curve obtained by joining B′ and the appropriate half of the tangent to B′ at z. We say that the point z can be “captured” by the arc A′, if an appropriate translation of A′ intersects B′ in two points determining an arc of B′ containing z in its relative interior.

Lemma 4.2. Let A′ and B′ be disjoint arcs of the boundary of a strictly convex body K corresponding to U and −U, respectively, such that they are not reflections of each other. Then one of the arcs has an endpoint which can be captured by the other arc.

Proof. Let z_{u} and z_{v} be the endpoints of A′, z_{−u} and z_{−v} those of B′.

Changing, if necessary, the coordinate system, we may assume that z_{u} = (0, 0), that u = (0, −1) and that locally the arc A′ is represented by the graph of a convex function defined in a right neighborhood of 0. Let B̃ = −(B′ + z_{u} − z_{−u}): B̃ is tangent to A′ in z_{u}.

Let us consider A′ and B̃: either B̃ ⊂ A′, or A′ ⊂ B̃ or there is a point (x, y) on one of the two arcs such that the other arc contains a point of the form (x′, y), with x′ > x.

The first two alternatives cannot happen since A′ and B̃ are strictly convex arcs with the same set of outer normals, and if B̃ ⊂ A′, or A′ ⊂ B̃, then A′ = B̃, contrary to the assumptions.

Let us assume that (x, y) ∈ A′: the map z → −z + (x, y) maps B̃ in a translate of B′ with one endpoint in (x, y) and a point (the image of (x′, y)) on the negative x−axis. The origin is thus an endpoint of A′ which is captured by B′. q.e.d.

The lemma will be used now to conclude that a body K is uniquely determined by its covariogram function among all the C_{+}^{2} bodies, showing that the arcs A′ and B′ of ∂K ∩ ∂H, as defined at the beginning of this section, can be extended, contradicting so their maximality.

By Lemma 4.2, there is an endpoint z of A′, say, which can be captured by B′: let T_{τ} be the translation that makes B′ capture z.

Changing, if necessary, the coordinate system, we may assume that z is the origin, and that the arc A′ is represented by the graph of a convex function g defined in a right neighborhood of 0, such that g(0) = 0 and g′(0) is finite. It is possible to extend the definition of the function g to a left neighborhood of 0 in such a way to represent a portion of ∂K adjacent to A′. Let f be the concave function whose graph is B′ + τ. The arc B′ + τ intersects A′ in a point (b, c) with b > 0 and moreover, changing possibly the translation T_{τ}, we may assume that B′ + τ also intersects the graph of g in a point with a negative abscissa a.

If we show that the covariogram function determines the boundary of K ∩ (K + τ), we are done, since this means that the arc A′ is not maximal in ∂K ∩ ∂H.

On the other hand the covariogram function gives the area of K ∩ (K +τ −(0, t)) for every t > 0. If we denote by [a_{t}, b_{t}] the interval where f(x) − t ≥ g(x), then

g_{K}(τ − (0, t)) = ∫_{a_{t}}^{b_{t}}(f(x) − t − g(x)) dx

= ∫_{a_{t}}^{0}(f(x) − t − g(x)) dx + ∫_{0}^{b_{t}}(f(x) − t − g(x)) dx.

The second integral in the last line is known for any t ∈ [0, f(0)], since f and g are, by assumption, known on [0, b]. Therefore we can deduce from the covariogram function the value of

∫_{a_{t}}^{0}(f(x) − t − g(x)) dx

for any t ∈ [0, f(0)]. By assumption f is known on [a, 0].

The next proposition will show that this information is sufficient to determine g on [a, 0].

Proposition 4.3. Suppose f is a given continuous strictly increasing function on [a, 0], with f(0) > 0.

If g is continuous and strictly decreasing on [a, 0] such that g(a) > f(a) and g(0) = 0, then g is uniquely determined in a left neighborhood of 0 by the areas of

(11)  {(x, y) : x ∈ [a, 0], g(x) ≤ y ≤ f(x) − t},

for 0 ≤ t ≤ f(0).

Proof. Let us denote by a_{t} the point where g(a_{t}) = f(a_{t}) − t: it is a_{0} < 0. The mapping h(t) = a_{t} is continuous since h is the inverse of the increasing and continuous mapping f − g restricted to [a_{0}, 0].

Let us denote by A(t) the area of (11). An elementary calculation shows that for every δ > 0,

δ · a_{t+δ} ≤ A(t) − A(t + δ) ≤ δ · a_{t}.

It follows that \frac{A(t)−A(t+δ)}{δ} → a_{t} = h(t), when δ → 0, because h is continuous.

We see from this that h is uniquely determined on its natural domain [0, f(0)], and so is therefore its inverse f − g, defined on [a_{0}, 0]. But f is determined by assumption, so g is determined on [a_{0}, 0], as claimed.

q.e.d.

In this section we have proved that the covariogram function determines a C_{+}^{2} convex body within the class C_{+}^{2}. In the next section we shall prove that uniqueness holds in the wider class of all convex bodies.

Remark 4.4. Note that the discussion preceding Proposition 4.3 only requires that K is strictly convex and that Proposition 4.3 itself requires even less on f and g, which are only supposed to be strictly increasing and decreasing, respectively, in addition to being continuous.

5. Regularity of the convex body from the covariogram function

In this section we shall prove that it is possible to recognize from the covariogram function g_{K} that the convex body K is C_{+}^{2}. This will be obtained in several steps.

If we want to recognize from g_{P} that P is a polygon it suffices to look at the support of g_{P}. On the other hand, if we want to know if K ∈ C^{m}, we have to consider also properties of the covariogram function, since its support does not give the information we require. To be convinced of this, note that the support of g_{K}, when K is a convex body of constant width, is a disc, and hence analytic, while we know that there are convex bodies of constant width which are not C^{1}.

Proposition 5.1. Let K ∈ C_{+}^{2} and H be two convex bodies having the same covariogram. Then H ∈ C_{+}^{2}.

First let us note that it follows immediately from the inspection of the support of g_{K} that H is strictly convex.

Moreover H belongs to C^{1}. This follows from the asymptotic behavior of the covariogram function near to the boundary of its support. If u is a normal at a point where the tangent does not exist, interior to the normal cone, then g_{H}(z_{u} − z_{−u} − tu) = O(t^{2}), while the fact that K ∈ C_{+}^{2} implies that g_{K}(z_{u} − z_{−u} − tu) behaves, when t tends to zero, as a constant times t^{3/2}, as shown in Lemma 2.1.

The second, and more difficult step, is to prove that ∂H is twice differentiable at every point. To achieve that, we need some lemmas.

Lemma 5.2. Let f be a strictly convex and C^{1} function in [a, b], with f(a) = f(b). Given 0 < r < b − a, let us consider the horizontal segment with endpoints on the graph of f having length r. Let us denote by (x_{1}(r), f(x_{1}(r))) and (x_{2}(r), f(x_{2}(r))), x_{1}(r) < x_{2}(r) these endpoints and with D(r) the distance between a given fixed point (x_{0}, y_{0}), with y_{0} < min_{[a,b]} f, and the line containing the segment.

Then, if for a given r_{0} f admits second derivative at x_{1}(r_{0}) and x_{2}(r_{0}), the second derivative D′′(r_{0}) exists. If on the other hand the second derivative of f does exist in one (and only one) of the two points x_{1}(r), x_{2}(r), then D′′(r_{0}) does not exist.

Proof. The functions x_{i}(r) are uniquely determined and satisfy the conditions

(12)  \{ \begin{matrix}f(x_{1}(r)) = f(x_{2}(r)) \\ x_{2}(r) − x_{1}(r) = r. \end{matrix}

Let c be such that f′(c) = 0: If we consider the equation f(u) = f(v), with u < c < v, since f ∈ C^{1} and f′(t) ≠ 0 for t ≠ c, it follows from the implicit function theorem that there exists φ ∈ C^{1}, defined on [a, c), such that v = φ(u) with φ′(u) < 0.

Given r > 0, we want to determine u such that v − u = r, i.e., φ(u) − u = r.

Since \frac{d}{du}(φ(u) − u) < 0, the function φ(u) − u is invertible. Let us denote the inverse by x_{1}(r). Clearly x_{1}(r) ∈ C^{1} and also x_{2}(r) = x_{1}(r) + r ∈ C^{1}.

We may differentiate therefore (12) with respect to r to obtain

\frac{d}{dr} x_{1}(r) = \frac{f′(x_{2}(r))}{f′(x_{1}(r)) − f′(x_{2}(r))}

and

\frac{d}{dr} x_{2}(r) = \frac{f′(x_{1}(r))}{f′(x_{1}(r)) − f′(x_{2}(r))}.

The function D(r) has the simple expression

D(r) = f(x_{1}(r)) − y_{0}.

Differentiating the right-hand side, we get

D′(r) = f′(x_{1})\frac{d}{dr} x_{1}(r) = \frac{f′(x_{2}(r))f′(x_{1}(r))}{f′(x_{1}(r)) − f′(x_{2}(r))}

= \frac{1}{\frac{1}{f′(x_{1}(r))} − \frac{1}{f′(x_{2}(r))}} ,

and from the last identity we get immediately the conclusion. q.e.d.

Lemma 5.3. Suppose H is a C^{1} plane convex body. Given v ∈ S^{1} and r > 0, let D_{H}(r, v) be the distance between the two chords of H parallel to v and having length r. If for given r_{0} and v_{0}, ∂H admits curvature at all the four endpoints of the two corresponding chords, then \frac{∂^{2}}{∂r^{2}} D_{H}(r_{0}, v_{0}) exists. If on the other hand ∂H does not admit curvature at exactly one of the endpoints, then \frac{∂^{2}}{∂r^{2}} D_{H}(r_{0}, v_{0}) does not exist.

Proof. We may suppose v_{0} = (0, 1). The function D_{H} can be expressed as the sum (or difference) of the distances of the two chords from a given point. The conclusion follows now from Lemma 5.2. q.e.d.

Proof of Proposition 5.1. Suppose that ∂H does not admit curvature in a point P. We may assume that the outer normal to H at P is (0, −1). In a polar coordinate system centered at P let θ_{0} denote the angular coordinate of the point of ∂H whose outer normal is (0, 1). For any θ ∈ (0, θ_{0}) let P_{2} = P_{2}(θ) be the point of ∂H with the property that the chord P_{2} − P is parallel to (cos θ, sin θ) and let P_{3} = P_{3}(θ), and P_{4} = P_{4}(θ) be points of ∂H with P_{4} − P_{3} = P_{2} − P, P_{4} ≠ P_{2}, P_{3} ≠ P.

Since H has the same covariogram function as K ∈ C_{+}^{2}, it follows from Lemma 5.3 that \frac{∂^{2}}{∂r^{2}} D_{H} exists for any r and v. The same lemma implies that for any θ ∈ (0, θ_{0}) the curvature does not exist in at least one of the points P_{i}, i = 2, 3, 4. We shall show that this contradicts the existence almost everywhere of the curvature.

Let us denote by s_{i}(θ) the length of the arc consisting of the points of ∂H which, in counterclockwise order, follow P and precede P_{i}, i = 2, 3, 4. Let us prove that the functions s_{i}(θ) are continuously differentiable.

We have

s_{2}(θ) = ∫_{0}^{θ} ∥γ′(t)∥ dt,

where γ(t) is the polar representation of ∂H in the polar coordinate system centered at P. Since ∂H is continuously differentiable, so is s_{2}(θ). The functions s_{2}(θ), s_{3}(θ) and s_{4}(θ) are related by the following equations, where P = (x_{1}, y_{1}):

(y(s_{2}) − y_{1}) cos θ − (x(s_{2}) − x_{1}) sin θ = 0
(y(s_{4}) − y(s_{3})) cos θ − (x(s_{4}) − x(s_{3})) sin θ = 0
(y(s_{4}) − y(s_{3}))^{2} + (x(s_{4}) − x(s_{3}))^{2}
−(y(s_{2}) − y_{1})^{2} − (x(s_{2}) − x_{1})^{2} = 0.

From this system, using the fact that s_{2}(θ) ∈ C^{1}, we can deduce a system of two equations in s_{3}(θ) and s_{4}(θ) of the kind

\{ \begin{matrix}(y(s_{4}) − y(s_{3}))^{2} cos^{2} θ − (x(s_{4}) − x(s_{3}))^{2} sin^{2} θ = 0 \\ (y(s_{4}) − y(s_{3}))^{2} + (x(s_{4}) − x(s_{3}))^{2} = φ(θ), \end{matrix}

with φ ∈ C^{1} and φ(θ) > 0 for all θ ∈ (0, θ_{0}). Multiplying the second equation by cos^{2} θ and subtracting the first equation, we get

(x(s_{4}) − x(s_{3}))^{2} = φ(θ) cos^{2} θ

and taking the square root we get an equation of the kind

(13)  x(s_{4}) − x(s_{3}) = ψ_{1}(θ),

with ψ_{1} ∈ C^{1}.

Similar considerations lead to an equation of the kind

(14)  y(s_{4}) − y(s_{3}) = ψ_{2}(θ),

with ψ_{2} ∈ C^{1}, for all θ ∈ (0, θ_{0}).

The determinant of the Jacobian of the system (13), (14) with respect to s_{3} and s_{4} is

x′(s_{4})y′(s_{3}) − x′(s_{3})y′(s_{4}),

which is not zero by the strict convexity of H. This proves that s_{i}(θ) ∈ C^{1} for i = 2, 3, 4.

Let us prove that there exists an interval U ⊂ (0, θ_{0}) such that each mapping θ → P_{i}, i = 2, 3, 4, restricted to U, maps sets of positive measure to subsets of ∂H with positive measure.

This property is clear for the mapping P_{2}(θ), for any choice of the interval U.

The mapping P_{4} is not constant in (0, θ_{0}) because otherwise H would be centrally symmetric about (P + P_{4})/2. If H is centrally symmetric it is homothetic to its difference body H + (−H), which coincides with the support of g_{H} = g_{K} and its boundary has curvature in every point, violating the existence of P.

Now, the mapping P_{3} cannot be constant in some interval V. If it were so, then the arcs described by P_{2}(θ) and P_{4}(θ) for θ ∈ V would be translates of each other and this would violate the strict convexity of H.

The regularity C^{1} of the two mappings s_{3}(θ) and s_{4}(θ) implies then that there is an interval U where their derivatives with respect to θ never vanish. P_{3} and P_{4} satisfy in U the required property.

In conclusion, let us denote by A_{i}, for i = 2, 3, 4, the subsets of U where ∂H does not admit curvature at P_{i}, respectively. We have proved that A_{2} ∪ A_{3} ∪ A_{4} = U and therefore at least one of the A_{i}’s has positive measure. But then P_{i}(A_{i}) would be a subset of ∂H having positive measure, where ∂H has no curvature, which is impossible.

To prove that H ∈ C_{+}^{2}, we have to prove that the curvature of H is continuous.

Let us observe that the existence of the curvature of H at every point allows us to conclude, using the same arguments as in Lemma 2.1 that

(15)  {τ_{H}(u), τ_{H}(−u)} = {τ_{K}(u), τ_{K}(−u)}.

We shall show that (15) and the continuity of τ_{K} implies the continuity of τ_{H}.

If in u_{0} it is τ_{K}(u) = τ_{K}(−u), then the continuity of τ_{H} at u_{0} and −u_{0} follows immediately from (15). If on the other hand

τ_{K}(u_{0}) ≠ τ_{K}(−u_{0}),

let us take an appropriate neighborhood U of u_{0} and a constant c between τ_{K}(u) and τ_{K}(−u), such that

(16)  τ_{K}(u) ≠ c, τ_{K}(−u) ≠ c for any u ∈ U.

If τ_{H} is discontinuous at u_{0}, then there exist in any neighborhood of u_{0} points u such that τ_{H}(u) = τ_{K}(u) and points v such that τ_{H}(v) = τ_{K}(−v), and therefore τ_{H} would take values arbitrarily close to τ_{K}(u_{0}) and other values arbitrarily close to τ_{K}(−u_{0}). But since τ_{H} is a derivative, it has the Darboux property ([34], p. 93) but this contradicts the fact that τ_{H}(u) ≠ c for all u ∈ U. q.e.d.

6. A genericity result

Definition 6.1. If K and H are two convex bodies in ℝ^{m}, the Nikodym distance between them is defined by

δ_{N}(K, H) = λ_{m}(K △ H).

Here △ denotes the symmetric difference between the two sets. It is well known that on the class K_{m} of all convex bodies in ℝ^{m},

the Hausdorff distance δ and the Nikodym distance induce the same topology, and it is also well known that K_{m} is a locally compact and hence a Baire space ([10]). When speaking of most elements of K_{m}, we mean all elements with a meager set (i.e., a countable union of nowhere dense sets) of exceptions.

Given two convex bodies K, we will denote by δ(K, H) the infimum (by compactness it is in fact a minimum) of all the distances δ(K, φ(H)), the infimum being taken over all the rigid motions φ.

Let us denote by S(0, r) the ball in ℝ^{m}, centered at the origin and with radius r.

Theorem 6.2. Most convex bodies in ℝ^{m} are uniquely determined (up to translation and reflection) by their covariogram function.

Proof. For m ≥ 3 the result has been proved by Goodey, Schneider and Weil ([12], Corollary to Theorem 2). Their method cannot be used, however, for m = 2 and we will give a direct proof for the planar case. If m = 1 it is easy to see that much more can be said, namely that the covariogram function determines any bounded closed interval up to translation.

Let us denote by A the class of all planar convex bodies which are not determined (up to translation and reflection) by their covariogram function.

Let us define

A_{n} = {K : K ∈ K_{2}, such that ∃H ∈ K_{2},

g_{K} = g_{H}, δ(K, H) ≥ \frac{1}{n}, H ⊂ S(0, n)\}.

Obviously, we have

A = ∪_{n}A_{n},

because if K is not uniquely determined (up to translation and reflection) by its covariogram function, there exists a convex body H (which is not a translation or reflection of K, and hence such that δ(K, H) > 0) with the same covariogram function. It follows then that there exists n such that δ(K, H) ≥ \frac{1}{n} and such that a translate of H is contained in S(0, n).

Let us prove now that A_{n} is closed. Let {K_{i}} be a sequence of convex bodies belonging to A_{n} converging to K_{0}. Let {H_{i}} be the corresponding sequence of sets with the same covariogram functions contained in S(0, n) for each i. By compactness there exists a convergent subsequence H_{i_{j}} → H_{0}. Obviously H_{0} ⊂ S(0, n) and it follows easily from the continuity of the distance that δ(K_{0}, H_{0}) ≥ \frac{1}{n}.

Moreover, K_{0} and H_{0} have the same covariogram function, since the mapping which assigns to each convex body its covariogram function is continuous by the inequality

|g_{K}(u) − g_{H}(u)| ≤ 2λ_{m}(K △ H) = 2δ_{N}(K, H), ∀u ∈ ℝ^{m}

and the equivalence of the two distances.

It follows that A is a countable union of closed sets, so its complement U is a countable intersection of open sets. On the other hand U is dense in K_{2}, as it contains all the convex planar polygons by [30], or, if we prefer, all C_{+}^{2} bodies by Theorem 1.1, and this proves the conclusion.

q.e.d.

References

[1] B. Blaschke, H.W. Engl, W. Grever & M.V. Klibanov, On the determination of convex bodies by projection functions, Bull. London Math. Soc. 29 (1997) 82–88.

[2] H.M. Berenyi & M.A. Fiddy, Application of homometric sets for beam manipulation, J. Opt. Soc. Am. A3 (1986) 373–375.

[3] R. Bakarat & G. Newsam, Necessary conditions for a unique solution to two-dimen-sional phase recovery, J. Math. Phys. 25 (1984) 3190–3193.

[4] M. Cowling, S. Disney, G. Mauceri & D. Müller, Damping oscillatory integrals, Invent. Math. 101 (1990) 237–260.

[5] H. Carnal & G.M. Fel’dman, Phase retrieval for probability measures on abelian groups, J. Theoret. Probab. 8 (1995) 717–725.

[6] H. Carnal & G.M. Fel’dman, Phase retrieval for probability measures on abelian groups II, J. Theoret. Probab. 10 (1997) 1065–1074.

[7] T.R. Crimmins & J.R. Fienup, Uniqueness of phase retrieval for functions with sufficiently disconnected support, J. Opt. Soc. Amer. 73 (1983) 218–221.

[8] J.R. Fienup, T.R. Crimmins & W. Holsztyński, Reconstruction of the support of an object from the support of its autocorrelation, J. Opt. Soc. Amer. 72 (1982) 610–624.

[9] R.J. Gardner, Geometric Tomography, Cambridge Univ. Press, New York, 1995.

[10] P.M. Gruber, Baire categories in convexity, in ‘Handbook of Convex Geometry’ (eds. P.M. Gruber & J.M. Wills), North-Holland, Amsterdam (1993) 1327–1346.

[11] M. Gage & R.S. Hamilton, The heat equation shrinking convex plane curves, J. Differential Geometry 23 (1986) 69–96.

[12] P. Goodey, R. Schneider & W. Weil, On the determination of convex bodies by projection functions, Bull. London Math. Soc. 29 (1997) 82–88.

[13] R.J. Gardner & G. Zhang, Affine inequalities and radial mean bodies, Amer. J. Math. 120 (1998) 493–504.

[14] C.S. Herz, Fourier transforms related to convex sets, Ann. Math. 75 (1962) 81–92.

[15] E. Hlawka, Integrale auf konvexe Körpern I, II, Monatsh. Math. 54 (1950) 1–36, 81–99.

[16] E.K. Haviland & A. Wintner, On the Fourier transform of distributions on convex curves, Duke Math. J. 2 (1936) 712–721.

[17] N.E. Hurt, Phase retrieval and zero crossing, Kluwer, Dordrecht, 1989.

the solution of the covariogram problem 197

[18] T. Isernia, G. Leone & R. Pierri, Role of support information and zero locations in phase retrieval by a quadratic approach, J. Opt. Soc. Amer. A16 (1999) 1845–1856.

[19] P. Jaming, Phase retrieval techniques for radar ambiguity problem, J. Fourier Anal. Appl. 5 (1999) 309–329.

[20] D.G. Kendall, On the number of lattice points inside a random oval, Quart. J. 19 (1948) 1–26.

[21] K. Kiêu, S. Souchet & J. Istas, Precision of systematic sampling and transitive methods, J. Statist. Plann. Inference 77 (1999) 263–279.

[22] M.V. Klibanov, P.E. Sacks & A.V. Tikhonravov, The phase retrieval problem, Inverse Problems 11 (1995) 1–28.

[23] A. Lešanovský, J. Rataj & S. Hojek, 0 − 1 sequences having the same number of (1 − 1) couples of given distances, Math. Bohem. 117 (1992) 271–282.

[24] G. Matheron, Random sets and integral geometry, Wiley, New York, 1975.

[25] G. Matheron, Le covariogramme géometrique des compacts convexes de ℝ^{2}, Technical report 2/86, Centre de Géostatistique, Ecole des Mines de Paris 54 (1986).

[26] C.L. Mallows & J.M. Clark, Linear-intercept distributions do not characterize plane sets, J. Appl. Prob. 7 (1970) 240–244.

[27] C.L. Mallows & J.M. Clark, Corrections to “Linear-intercept distributions do not characterize plane sets”, J. Appl. Prob. 8 (1971) 208–209.

[28] K.A. Marsh & J.M. Richardson, Probabilistic algorithm for phase retrieval, J. Opt. Soc. Amer. A5 (1988) 993–998.

[29] W. Nagel Geometric covariograms for pairs of parallel f-planes, Geobild ’89, A. Hubler et al. Ed., Akademie-Verlag, Berlin, 1991.

[30] W. Nagel, Orientation-dependent chord length distributions characterize convex polygons, J. Appl. Prob. 30 (1993) 730-736.

[31] A.N. Podkorytov, On the asymptotics of the Fourier transform on a convex curve, Vestnik Leningrad Univ. Math. 24 (1991) 57–65.

[32] J. Rosenblatt, Phase retrieval, Comm. Math. Phys. 95(3) (1984) 317–343.

[33] J. Rosenblatt & P.D. Seymour, The structure of homometric sets, SIAM J. Alg. Disc. Meth. 3 (1982) 343–350.

[34] W. Rudin, Principles of mathematical analysis, McGraw Hill, New York, 1964.

[35] J. Serra, Image analysis and mathematical morphology, Academic Press, London, [36] M. Schmitt, On two inverse problems in mathematical morphology; Chapter 5 in

Mathematical morphology in image processing, Marcel Dekker, New York (E.R. Dougherty ed.), 1993.

[37] D. Schott, Signal reconstruction from given phase of the Fourier transform using Fejér monotone methods, Discuss. Math. Differ. Incl. Control Optim. 20 (2000) 27–40.

[38] P. van Toorn & H.A. Ferweda, The problem of phase retrieval in light and electron microscopy of strong objects. III. Developments of methods for numerical solution, Optica Acta 23 (1976) 457–468.

Università degli Studi di Ferrara

44100 Ferrara, Italy (first and second authors)

Università degli Studi di Trieste 34100 Trieste, Italy