Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

10.3 Applications in Geometric Tomography

10.3 Applications in Geometric Tomography

If the Euclidean distance is substituted by the distance function arising from the 1-norm then we have another notion of generalized conics with applications in geometric tomography [58]. Geometrictomography focuses on problems of reconstructing homogeneous ( often convex) objects from tomographic data (X-rays, projections, sections etc.). A key theorem in this area states that any convex planar body can be determined by parallel X-rays in a set of four directions whose slopes have a transcendental cross-ratio [26].

Let K be a compact body (a compact set is called a body if it is the closure of its interior) in the coordinate plane,

F K ( x , y ) : = 1 A ( K ) f K ( x , y ) ,

(10.15)

where

f K ( x , y ) : = K d 1 ( ( x , y ) , ( α , β ) ) d α d β ,

A(K) is the area of K and

d 1 ( v , w ) = | v 1 - w 1 | + | v 2 - w 2 |

is the distance function induced by the taxicab norm (1-norm)

| ( x , y ) | 1 = | x | + | y | .

Excercise 10.3.1 Using the notatios

x < K : = { ( α , β ) K | x < α } , K < x : = { ( α , β ) K | α < x } ,

y < K : = { ( α , β ) K | y < β } , K < y : = { ( α , β ) K | β < y } ,

x = K : = { ( α , β ) K | α = x } , y = K : = { ( α , β ) K | β = y }

prove that

D 1 F K ( x , y ) = A ( K < x ) A ( K ) - A ( x < K ) A ( K ) ,

D 2 F K ( x , y ) = A ( K < y ) A ( K ) - A ( y < K ) A ( K ) .

Hint. For the proof see [57].

Corollary 10.3.2 The global minimizer of the generalized conic function associated to K bisects the area in the sense that the vertical and horizontal lines through this point cut the body K into two parts with equal area.

Using these formulas the partial derivatives can be expressed by the Cavalieri's principle as follows:

A ( K < x ) = - x Y ( s ) d s   a n d   A ( K < y ) = - y X ( t ) d t ,

where the functions X and Y give the one-dimensional measure of sections with the coordinate lines, respectively. These are called X-ray functions into the coordinate directions. Lebesgue's differentiation theorem shows that

D 1 D 1 F K ( x , y ) = 2 A ( K ) Y ( x )   a n d   D 2 D 2 F K ( x , y ) = 2 A ( K ) X ( y )

holds almost everywhere. Therefore the function 10.15 measuring the average "taxicab" distance can be considered as an accumulation of coordinate X-rays' information. The following figures show different polygons with the same coordinate X-rays to illustrate the difficulties of the reconstruction.

Figure 66: A convex polygon with coordinate X-rays I.

Figure 67: A convex polygon with coordinate X-rays II.

As we can see the inner singularities (together with the endpoints of the support intervals) of the coordinate X-ray functions determine a grid having the possible vertices. This means (among others) that we have only finitely many different polygons with the same coordinate X-rays. Another important consequence is that any convex polygon can be successively determined[14] by three X-rays because we can choose the third direction in such a way that it is not parallel to any line joining the points of the grid.

Excercise 10.3.3 Prove that the singularities of the coordinate X-rays correspond to the vertices of the convex polygon in the plane.

Hint. Any convex polygon P in the plane can be written into the form

P = { ( x , y ) | f ( x ) y g ( x ) } , a x b

where f is a convex, g is a concave function of the variable. Therefore the vertical X-ray function has the simple form Y(x)=g(x) - f(x). On the other hand the support of Y is an interval [a,b]. It can be easily seen that the difference of a concave and a convex function is concave and, consequently, the X-ray functions of convex compact planar bodies are continuous and differentiable almost anywhere. Moreover,if Y is differentiable at an inner point x then

f ' + ( x ) - f ' - ( x ) = g ' + ( x ) - g - ' ( x ) ,

where the signs + and - refer to the right and left hand side derivatives of the functions, respectively. Since f is convex,

f ' - ( x ) f ' + ( x )

and, consequently, for a concave function,

g ' - ( x ) g + ' ( x )

which means that

f ' - ( x ) = f ' + ( x )   a n d   g ' - ( x ) g + ' ( x ) ,

i.e. Y is differentiable at x if and only if P has no vertex along the vertical line at x.

Definition The box of a compact convex planar body means the circumscribed rectangle with parallel sides to the coordinate directions.

Excercise 10.3.4 Prove that the set of compact convex planar bodies having the same box is convex in the sense that if K and L have a common box then it isa box for any convex combination

M : = λ K + ( 1 - λ ) L

too. Conclude that

Y M ( x ) λ Y K ( x ) + ( 1 - λ ) Y L ( x ) ,

(10.16)

X M ( y ) λ X K ( y ) + ( 1 - λ ) X L ( y ) .

(10.17)

Express the coordinate X-rays of M in terms of the coordinate X-rays of K and L.

Hint. Use the infimal convolution of functions.

Inequalities 10.16 and 10.17 imply, by the Cavalieri's principle, that the volume is a concave function on the set of compact convex planar bodies having a common box; in general see the Brunn-Minkowski inequality in subsection 4.2.1. As another consequence we have

f λ K + ( 1 - λ ) L λ f K + ( 1 - λ ) f L .

For generalizations and applications see [59]. The goal of this section is to present a positive reconstructing result for the class of generalized 1-conics

f K ( x , y ) = c o n s t .

The proof will be presented in a more general situation. Let K be a compact body and consider the distance function

d p ( ( x , y ) , ( α , β ) ) = ( | x - α | p + | y - β | p ) 1 / p

induced by the p-norm, where p is greater or equal than one. Define the class of generalized p-conics as the boundary of the level sets

f K p ( x , y ) c

(10.18)

of generalized p-conic functions

f K p ( x , y ) : = K d p ( ( x , y ) , ( α , β ) ) d α d β ; e s p e c i a l l y f K = f K 1 .

Theorem 10.3.5 Let C be a solid generalized p-conic and suppose that C* is a compact body with the same area as C. If the generalized p-conic functions associated to C and C* coincide then C is equal to C* except on a set of measure zero.

Proof Let C be the level set 10.18 of the generalized p-conic function associated with K and suppose that C* is a compact body with the same area as C such that the generalized p-conic functions associated with C and C* coincide. By the Fubini theorem

C f K p = K f C p = K f C * p = C * f K p

(10.19)

and thus

C \ C * f K p = C f K p - C C * f K p = C * f K p - C C * f K p = C * \ C f K p .

(10.20)

Since

C \ C * f k p c A ( C \ C * )

(10.21)

and

C * \ C f k p c A ( C * \ C )

(10.22)

we have that

A ( C \ C * ) A ( C * \ C ) .

(10.23)

But C and C* have the same area and, consequently, equality holds in formula 10.23. Therefore equalities hold in both 10.21 and 10.22. This means that C does not contain any subset of positive measure which is disjoint from C* and vice versa:

A ( C \ C * ) = A ( C * \ C ) = 0

(10.24)

showing that C is equal to C* except on a set of measure zero. ▮

Corollary 10.3.6 Let C and C* be generalized p-conics. If the generalized p-conic functions associated to C and C* coincide then C=C*.

Proof Since both of the sets C and C* are generalized p-conics they have a symmetric role in 10.23 showing that they have the same area. To finish the proof we use the previous theorem for the compact convex sets C and C*.

Corollary 10.3.7 Generalized 1-conics are determined by their X-rays in the coordinate directions among compact bodies.

Proof In case of p=1 the condition for the generalized conic functions implies automatically that C and C* have the same area. To finish the proof we use the previous theorem for the sets C and C*.

Remark The problem of determination of convex bodies by a finite set of X-rays was posed by P. C. Hammer at the A.M.S. Symposium on Convexity in 1961. X-rays can be considered as original but special examples for tomographic quantities. Another question is how to recognize a convex planar body from its angle function. The notion was introduced by J. Kincses [34]. Conditions for distinguishability are formulated in terms of the tangent homomorphism using thetheory of dynamical systems [33]. Like the coordinate X-ray pictures the author prove that distinguishability is typical in the sense of Baire category: a set is of first category if it is the countable union of nowhere dense sets (not typical cases) and of second category otherwise (typical cases).

Example Consider the square

N : = c o n v ( 0,0 ) , ( 1,0 ) , ( 1,1 ) , ( 0,1 ) ;

for any point (x,y) in N

f N ( x , y ) = ( x - ( 1 / 2 ) ) 2 + ( y - ( 1 / 2 ) ) 2 + ( 1 / 2 )

and circles can be interpreted as generalized 1-conics with N as the set foci. Therefore they are determined by their X-rays into the coordinate directions among compact bodies.

Excercise 10.3.8 Prove that for any point in N

f N ( x , y ) = ( x - ( 1 / 2 ) ) 2 + ( y - ( 1 / 2 ) ) 2 + ( 1 / 2 ) .

Excercise 10.3.9 Consider the triangle

T : = c o n v ( 0,0 ) , ( 1,0 ) , ( 1,1 ) .

Prove that for any point in the box of T

f T ( x , y ) = x 3 - y 3 3 + y 2 - x - y 2 + 1 2 .

Excercise 10.3.10 Let P be a convex polygon in the plane. Prove that generalized conics with P as the set of foci are the union of adjacent algebraic curves of degree at most three.

Hint. For the partition of the level curves use the grid of the polygon determined by the vertices.

Excercise 10.3.11 Consider the unit disk

D = { ( x , y ) | x 2 + y 2 1 } .

Prove that for any point in the box of D

f D ( x , y ) = 2 x 2 1 - x 2 + 2 x a r c s i n ( x ) + 4 3 ( 1 - x 2 ) 3 / 2 +

2 y 2 1 - y 2 + 2 y a r c s i n ( y ) + 4 3 ( 1 - y 2 ) 3 / 2 .