On the Algorithmic Complexity of Minkowski's Reconstruction Theorem

In 1903 Minkowski showed that, given pairwise different unitvectors µ₁, ..., µ_m in Euclidean n-space Rⁿ whichspan Rⁿ, and positive reals µ₁, ..., µ_m such that^m_i=1µ_iµ_i = 0, there exists a polytope P in Rⁿ, uniqueup to translation, with outer unit facet normals µ₁, ...,µ_m and corresponding facet volumes µ₁, ..., µ_m.This paper deals with the computational complexity of the underlyingreconstruction problem, to determine a presentation of P asthe intersection of its facet halfspaces. After a natural reformulationthat reflects the fact that the binary Turing-machine modelof computation is employed, it is shown that this reconstructionproblem can be solved in polynomial time when the dimensionis fixed but is #P-hard when the dimension is part of the input. The problem of ‘Minkowski reconstruction’ has variousapplications in image processing, and the underlying data structureis relevant for other algorithmic questions in computationalconvexity.     

Successive Determination and Verification of Polytopes by their X-Rays

It is shown that each convex polytope P in ^d can be verifiedby ([d/(d–k)] + 1) k-dimensional X-rays. This means thatP is uniquely determined by these X-rays and the choice of thedirection of each X-ray depends only on P. Examples are constructedto show that in general this number cannot be reduced. Further,it is shown that each convex polytope P in ³ can be successivelydetermined by only two one-dimensional X-rays. This means thatP is uniquely determined by one X-ray taken in an arbitrarydirection together with another whose direction depends onlyon the first X-ray. The results extend those for the case d= 2 of Giering and of Edelsbrunner and Skiena.     

A Classification of Horizontally Homothetic Submersions from Space Forms of Nonnegative Curvature

In this paper, it is proved that for n 2, any horizontallyhomothetic submersion : Rⁿ⁺¹ (Nⁿ, h) is a Riemannian submersionup to a homothety. It is also shown that if : Sⁿ⁺¹ (Nⁿ, h)is a horizontally homothetic submersion, then n = 2m, (Nⁿ, h)is isometric to CP^m and, up to a homothety, is a standard Hopffibration S^2m+1 CP^m. 2000 Mathematics Subject Classification53C20, 53C12.     

A Peak Point Theorem for Uniform Algebras Generated by Smooth Functions on Two-Manifolds

We establish the peak point conjecture for uniform algebrasgenerated by smooth functions on two-manifolds: if A is a uniformalgebra generated by smooth functions on a compact smooth two-manifoldM, such that the maximal ideal space of A is M, and every pointof M is a peak point for A, then A = C(M). We also give an alternativeproof in the case when the algebra A is the uniform closureP(M) of the polynomials on a polynomially convex smooth two-manifoldM lying in a strictly pseudoconvex hypersurface in Cⁿ.     

Determination of a Convex Body from Minkowski Sums of its Projections

For a convex body K in R^d and 1 K d – 1, let P_K (K)be the Minkowski sum (average) of all orthogonal projectionsof K onto k-dimensional subspaces of R^d. It is Known that theoperator P_k is injective if kd/2, k=3 for all d, and if k =2, d 14. It is shown that P_2k (K) determines a convex body K among allcentrally symmetric convex bodies and P_2k+1(K) determines aconvex body K among all bodies of constant width. Correspondingstability results are also given. Furthermore, it is shown thatany convex body K is determined by the two sets P_k (K) and P_k'(K) if 1 < k < k'. Concerning the range of P_k , 1 k d–2, it is shown that its closure (in the Hausdorff-metric)does not contain any polytopes other than singletons.     

A Lie Theoretic Approach to Thompson's Theorems on Singular Values-Diagonal Elements and Some Related Results

Thompson's famous theorems on singular values–diagonalelements of the orbit of an nxn matrix A under the action (1)U(n) U(n) where A is complex, (2) SO(n) SO(n), where A isreal, (3) O(n) O(n) where A is real are fully examined. Coupledwith Kostant's result, the real semi-simple Lie algebra so_n,n yields (2) and hence (3) and the sufficient part (the hardpart) of (1). In other words, the curious subtracted term(s)are well explained. Although the diagonal elements correspondingto (1) do not form a convex set in Cⁿ, the projection of thediagonal elements into Rⁿ (or iRⁿ) is convex and the characterizationof the projection is related to weak majorization. An elementaryproof is given for this hidden convexity result. Equivalentstatements in terms of the Hadamard product are also given.The real simple Lie algebra su_{n, n} shows that such a convexityresult fits into the framework of Kostant's result. Convexityproperties and torus relations are studied. Thompson's resultson the convex hull of matrices (complex or real) with prescribedsingular values, as well as Hermitian matrices (real symmetricmatrices) with prescribed eigenvalues, are generalized in thecontext of Lie theory. Also considered are the real simple Liealgebras so_{p, q} and so_{p, q}, p < q, which yield the rectangularcases. It is proved that the real part and the imaginary partof the diagonal elements of complex symmetric matrices withprescribed singular values are identical to a convex set inRⁿ and the characterization is related to weak majorization.The convex hull of complex symmetric matrices and the convexhull of complex skew symmetric matrices with prescribed singularvalues are given. Some questions are asked.     

Volume Estimate Via Total Curvature in Hyperbolic Spaces

Let D Hⁿ(–k²) be a convex compact subset of the hyperbolicspace Hⁿ(–k²) with non-empty interior and smooth boundary.It is shown that the volume of D can be estimated by the totalcurvature of D. More precisely, , where K denotes the Gauss–Kronecker curvature of D andVol(S^n–1) denotes the Euclidean volume of the sphere.2000 Mathematics Subject Classification 53C21.     

An Euler-Type Version of the Local Steiner Formula for Convex Bodies

The purpose of this note is to establish a new version of thelocal Steiner formula and to give an application to convex bodiesof constant width. This variant of the Steiner formula generalizesresults of Hann [3] and Hug [6], who use much less elementarytechniques than the methods of this paper. In fact, Hann askedfor a simpler proof of these results [4, Problem 2, p. 900].We remark that our formula can be considered as a Euclideananalogue of a spherical result proved in [2, p. 46], and thatour method can also be applied in hyperbolic space. For some remarks on related formulas in certain two-dimensionalMinkowski spaces, see Hann [5, p. 363]. For further information about the notions used below, we referto Schneider's book [9]. Let Kⁿ be the set of all convex bodiesin Euclidean space Rⁿ, that is, the set of all compact, convex,non-empty subsets of Rⁿ. Let S^n–1 be the unit sphere.For KKⁿ, let NorK be the set of all support elements of K, thatis, the pairs (x, u)RⁿxS^n–1 such that x is a boundarypoint of K and u is an outer unit normal vector of K at thepoint x. The support measures (or generalized curvature measures)of K, denoted by ₀(K.), ..., _n–1(K.), are the unique Borelmeasures on RⁿxS^n–1 that are concentrated on NorK andsatisfy [formula] for all integrable functions f:RⁿR; here denotes the Lebesguemeasure on Rⁿ. Equation (1), which is a consequence and a slightgeneralization of Theorem 4.2.1 in Schneider [9], is calledthe local Steiner formula. Our main result is the following.1991 Mathematics Subject Classification 52A20, 52A38, 52A55.     

A Criterion for Finite Topological Determinacy of Map-Germs

Let f, g: (Rⁿ, 0) (R^p, 0) be two C map-germs. Then f and gare C⁰-equivalent if there exist homeomorphism-germs h and lof (Rⁿ, 0) and (R^p, 0) respectively such that g = l f h^–1.Let k be a positive integer. A germ f is k-C⁰-determined ifevery germ g with j^k g(0) = j^k f(0) is C⁰-equivalent to f. Moreover,we say that f is finitely topologically determined if f is k-C⁰-determinedfor some finite k. We prove a theorem giving a sufficient conditionfor a germ to be finitely topologically determined. We explainthis condition below. Let N and P be two C manifolds. Consider the jet bundle J^k(N,P) with fiber J^k(n, p). Let z in J^k(n, p) and let f be suchthat z = j^kf(0). Define Whether (f) < k depends only on z, not on f. We can thereforedefine the set Let W^k(N, P) be the subbundle of J^k(N, P) with fiber W^k(n, p).Mather has constructed a finite Whitney (b)-regular stratificationS^k(n, p) of J^k(n, p) – W^k(n, p) such that all strata aresemialgebraic and K-invariant, having the property that if S^k(N,P) denotes the corresponding stratification of J^k(N, P) –W^k(N, P) and f C(N, P) is a C map such that j^kf is multitransverseto S^k(N, P), j^kf(N) W^k(N, P) = and N is compact (or f is proper),then f is topologically stable. For a map-germ f: (Rⁿ, 0) (R^p, 0), we define a certain ojasiewiczinequality. The inequality implies that there exists a representativef: U R^p such that j^kf(U – 0) W^k (Rⁿ, R^p = and suchthat j^kf is multitransverse to S^k (Rⁿ, R^p) at any finite setof points S U – 0. Moreover, the inequality controlsthe rate j^kf becomes non-transverse as we approach 0. We showthat if f satisfies this inequality, then f is finitely topologicallydetermined. 1991 Mathematics Subject Classification: 58C27.     

On the Least Q-order of Convergence of Variable Metric Algorithms

It is shown in this paper that the infimum of the Q-order ofthe convergence of variable metric algorithms is only 1, eventhough the objective function is twice continuously differentiableand uniformly convex. It is shown by example that the Q-ordercan be 1 + 1/N for any large N, though the R-order is (1+N)^1/2.     

Linear Systems and Quotients of Projective Space

A complete characterization of the categorical quotients of(P¹)ⁿ by the diagonal action of SL(2, C) with respect to anypolarization is given by M. Polito, in ‘SL(2, C)-quotientsde (P¹)ⁿ’, C. R. Acad. Sci. Paris Sér. I 321 (1995)1577–1582. In this paper, these categorical quotientsare obtained by certain linear systems on P^n–3, dependingon the given polarization. 2000 Mathematics Subject Classification14L24, 14L30     

Plane with A{infty}-Weighted Metric not Bilipschitz Embeddable to Rn

A planar set G R² is constructed that is bilipschitz equivalentto (G,d^z), where (G, d) is not bilipschitz embeddable to anyuniformly convex Banach space. Here, Z (0, 1) and d^z denotesthe zth power of the metric d. This proves the existence ofa strong A weight in R², such that the corresponding deformedgeometry admits no bilipschitz mappings to any uniformly convexBanach space. Such a weight cannot be comparable to the Jacobianof a quasiconformal self-mapping of R². 2000 Mathematics SubjectClassification 54E40 (primary); 30C62, 30C65, 28A80 (secondary).     

On Closed Sets with Convex Projections

A shadow of a subset A of Rⁿ is the image of A under a projectiononto a hyperplane. Let C be a closed nonconvex set in Rⁿ suchthat the closures of all its shadows are convex. If, moreover,there are n independent directions such that the closures ofthe shadows of C in those directions are proper subsets of therespective hyperplanes then it is shown that C contains a copyof R^n–2. Also for every closed convex set B ‘minimalimitations’ C of B are constructed, that is, closed subsetsC of B that have the same shadows as B and that are minimalwith respect to dimension.     

Jacobi Fields Along Harmonic 2-Spheres in CP2 are Integrable

The paper shows that any Jacobi field along a harmonic map fromthe 2-sphere to the complex projective plane is integrable (thatis, is tangent to a smooth variation through harmonic maps).This provides one of the few known answers to the problem ofintegrability, which was raised in different contexts of geometryand analysis. It implies that the Jacobi fields form the tangentbundle to each component of the manifold of harmonic maps fromS² to CP² thus giving the nullity of any such harmonic map;it also has a bearing on the behaviour of weakly harmonic E-minimizingmaps from a 3-manifold to CP² near a singularity and the structureof the singular set of such maps from any manifold to CP².     

Convex Bodies with Homothetic Sections

We prove that if K is a convex body in Eⁿ⁺¹, n2, and p₀ is apoint of K with the property that all n-sections of K throughp₀ are homothetic, then K is a Euclidean ball.     

Vector Majorization Via Hessenberg Matrices

In this paper it is proved that, for real n-vectors x and y,x is majorized by y if and only if x = PHQy for some permutationmatrices P, Q, and for some doubly stochastic matrix H whichis a direct sum of doubly stochastic Hessenberg matrices. Thisresult reveals that any n-vector which is majorized by a vectory can be expressed as a convex combination of at most (n² –n + 2)/2 permutations of y.     

S-integral preperiodic points for dynamical systems over number fields

Given a rational map :¹¹ defined over a number field K, we provea finiteness result for -preperiodic points which are S-integralwith respect to a non-preperiodic point P, provided that P satisfiesa certain local condition at each place. This verifies a specialcase of a conjecture of Ih.     

The Normal Holonomy Group of Kahler Submanifolds

We study the (restricted) holonomy group Hol() of the normalconnection (shortened to normal holonomy group) of a Kählersubmanifold of a complex space form. We prove that if the normalholonomy group acts irreducibly on the normal space then itis linear isomorphic to the holonomy group of an irreducibleHermitian symmetric space. In particular, it is a compact groupand the complex structure J belongs to its Lie algebra. We prove that the normal holonomy group acts irreducibly ifthe submanifold is full (that is, it is not contained in a totallygeodesic proper Kähler submanifold) and the second fundamentalform at some point has no kernel. For example, a Kähler–Einsteinsubmanifold of CPⁿ has this property. We define a new invariant µ of a Kähler submanifoldof a complex space form. For non-full submanifolds, the invariantµ measures the deviation of J from belonging to the normalholonomy algebra. For a Kähler–Einstein submanifold,the invariant µ is a rational function of the Einsteinconstant. By using the invariant µ, we prove that thenormal holonomy group of a not necessarily full Kähler–Einsteinsubmanifold of CPⁿ is compact, and we give a list of possibleholonomy groups. The approach is based on a definition of the holonomy algebrahol(P) of an arbitrary curvature tensor field P on a vectorbundle with a connection and on a De Rham type decompositiontheorem for hol(P). 2000 Mathematics Subject Classification53C40 (primary), 53B25 (secondary).     

Totally Real Minimal Surfaces with Non-Circular Ellipse of Curvature in the Nearly Kahler S6

In [2] we discussed almost complex curves in the nearly KählerS⁶. These are surfaces with constant Kähler angle 0 or and, as a consequence of this, are also minimal and have circularellipse of curvature. We also considered minimal immersionswith constant Kähler angle not equal to 0 or , but withellipse of curvature a circle. We showed that these are linearlyfull in a totally geodesic S⁵ in S⁶ and that (in the simplyconnected case) each belongs to the S¹-family of horizontallifts of a totally real (non-totally geodesic) minimal surfacein CP². Indeed, every element of such an S¹-family has constantKähler angle and in each family all constant Kählerangles occur. In particular, every minimal immersion with constantKähler angle and ellipse of curvature a circle is obtainedby rotating an almost complex curve which is linearly full ina totally geodesic S⁵.     

Extremal mean width when covering the 1-skeleton

For a given convex body K in ^d, let D_n be the compact convexset of maximal mean width whose 1-skeleton can be covered byn congruent copies of K. Based on the fact that the mean widthis proportional to the average perimeter of two-dimensionalprojections, it is proved that D_n is close to being a segmentfor large n.