Cutting a Convex Polyhedron Out of a Sphere

Given a convex polyhedron P of n vertices inside a sphere Q, we give an O(n ³)-time algorithm that cuts P out of Q by using guillotine cuts and has cutting cost O(log² n) times the optimal.     

AnO(n logn) algorithm for computing the link center of a simple polygon

We present an algorithm that determines the link center of a simplen-vertex polygonP inO(n logn) time. The link center of a simple polygon is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. The link distance between two pointsx andy insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx andy. Using our algorithm we also obtain anO(n logn)-time solution to the problem of determining the link radius ofP. The link radius ofP is the maximum link distance from a point in the link center to any vertex ofP. Both results are improvements over theO(n ²) bounds previously established for these problems. The research of J.-R. Sack was supported by the Natural Sciences and Engineering Research Council of Canada.     

Remarques sur les systemes dynamiques donnes avec plusieurs facteurs

Two Bernoulli shifts are given, (X, T) and (X′, T′), with independent generatorsR=P ∨Q andR′=P′ ∨Q′ respectively. (R andR′ are finite). One can chooseR such that if (X′, T′) can be made a factor of (X, T) in such a way that (P′) _T′ and (Q′) _T′ are full entropy factors of (P) _T and (Q) _T respectively thend (P ∨Q)=d(P′ ∨Q′). In addition it is proved that if (X, T) is a Bernoulli shift and ifS is a measure preserving transformation ofX that has the same factor algebras asT thenS=T orS=T ⁻¹. A tool for this proof, which may be of independent interest is a relative version for very weak Bernoullicity.

---

---

Equipe de Recherche n^o 1 “Processus stochastique et applications” dépendant de la Section n^o 1 “Mathématiques, Informatique” associée au C.N.R.S.     

Characterizations of Some Product Manifolds by Their Spectrum

Let Sⁿ(c) denote the n-dimensional Euclidean sphere of constant sectional curvature c and denote by CPⁿ(c) the complex projective space of complex dimension n and of holomorphic sectional curvature c. In this paper, we obtain some characterizations of the manifolds S²(c) × S²(c′), S⁴(c) × S⁴(c′), CP²(c) × CP²(c′) by their spectrum.     

Characterizations of Some Product Manifolds by Their Spectrum

Let Sⁿ(c) denote the n-dimensional Euclidean sphere of constant sectional curvature c and denote by CPⁿ(c) the complex projective space of complex dimension n and of holomorphic sectional curvature c. In this paper, we obtain some characterizations of the manifolds S²(c) × S²(c′), S⁴(c) × S⁴(c′), CP²(c) × CP²(c′) by their spectrum.     

Distributed algorithms solving the updating problems

In this paper, we consider the updating problems to reconstruct the biconnected-components and to reconstruct the weighted shortest path in response to the topology change of the network. We propose two distributed algorithms. The first algorithm solves the updating problem that reconstructs the biconnected-components after the several processors and links are added and deleted. Its bit complexity is O((n′ +a +d) logn′), its message complexity is O(n′ +a +d), the ideal time complexity isO(n′), and the space complexity isO(e logn +e′ logn′). The second algorithm solves the updating problem that reconstructs the weighted shortest path. Its message complexity and ideal-time complexity areO(u ² +a +n′) respectively.     

Thermocapillary motion of deformable fluid particles in tubes

The boundary integral technique is used to study the effect of deformation on the steady, creeping, thermocapillary migration of a fluid particle under conditions of axisymmetry, negligible thermal convection and an insulated tube wall. The spherical radius of the fluid particle (i.e. the radius as if the particle were a sphere, a ′= (3V _p ^′ /4π)^1/3, V _p ^′ is the particle volume) and that of the tube are denoted, respectively, by a′and b′. For small capillary numberCa = 0.05, only for a large fluid particle (a′/b′ = 0.8) is deformation significant. Fora′/b′= 0.8, hydrodynamic stresses squeeze the particle, reduce the interaction of the particle with the wall and thereby increase the terminal velocity. For small particles a′/b′< 0.8 and Ca = 0.05 the fluid particles translate as spheres, due to the fact that the fluid particle is too far away from the wall to be subject to distending hydrodynamic stresses. The deformable particle moves faster than a spherical one in the thermocapillary migration. The increase in velocity with capillary number is larger for thermocapillary motion than for buoyancy.     

Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem

The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in ℝ ^d , incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radius r(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ ⁴/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(n ^Δ+1 dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space. An extended abstract appeared in ACM–SIAM Symposium on Discrete Algorithms, 2006. Work was done when J. Gao was with Center for the Mathematics of Information, California Institute of Technology. Work was done when M. Langberg was a postdoctoral scholar at the California Institute of Technology. Research supported in part by NSF grant CCF-0346991. Research of L.J. Schulman supported in part by an NSF ITR and the Okawa Foundation.     

Compact minimal hypersurfaces with index one in the real projective space

Let M ⁿ be a compact (two-sided) minimal hypersurface in a Riemannian manifold . It is a simple fact that if has positive Ricci curvature then M cannot be stable (i.e. its Jacobi operator L has index at least one). If is the unit sphere and L has index one, then it is known that M must be a totally geodesic equator.?We prove that if is the real projective space , obtained as a metric quotient of the unit sphere, and the Jacobi operator of M has index one, then M is either a totally geodesic sphere or the quotient to the projective space of the hypersurface obtained as the product of two spheres of dimensions n ₁, n ₂ and radius R ₁, R ₂, with and . Received: June 6, 1998     

A class of oscillatory singular integrals on triebel-lizorkin spaces

The boundedness on Triebel-Lizorkin spaces of oscillatory singular integral operator T in the form e^i｜x｜^aΩ（x）｜x｜^-n is studied,where a∈R,a≠0,1 and Ω∈L^1（S^n-1） is homogeneous of degree zero and satisfies certain cancellation condition. When kernel Ω（x＇ ）∈Llog＋L（S^n-1 ）, the Fp^a,q（R^n） boundedness of the above operator is obtained. Meanwhile ,when Ω（x） satisfies L^1- Dini condition,the above operator T is bounded on F1^0,1 （R^n）.     

Exponential decay for distributed bilinear control systems with damping

Let Ω be a bounded open domain in ℝ ^N ,A an unbounded, selfadjoint, positive and coercive linear operator onL ² (Ω). We consider feedback stabilization for the distributed bilinear control systemy″(t)+Ay(t)+Dy′(t)+u(t)By(t)=0, whereD andB are linear bounded operators fromL ²(Ω) toL ²(Ω). Under suitable assumptions onB andD, a nonlinear feedback ensuring uniform exponential decay of solutions is given. Various applications to vibrating processes are presented.     

On generators of ideals defining projective toric varieties

 For any ample line bundle L on a projective toric variety of dimension n, it is proved that the line bundle L ^⊗i is normally generated if i is greater than or equal to n−1, and examples showing that this estimate is best possible are given. Moreover we prove an estimate for the degree of the generators of the ideals defining projective toric varieties. In particular, when L is normally generated, the defining ideal of the variety embedded by the global sections of L has generators of degree at most n+1. When the variety is embedded by the global sections of L ^⊗(n−1) , then the defining ideal has generators of degree at most three. Received: 11 July 2001 / Revised version: 17 December 2001     

Wavelet expansions of fractal measures

Let μ be a measure on ℝⁿ that satisfies the estimate μ(B _r(x))≤cr ^α for allx ∈ ℝⁿ and allr ≤ 1 (B _r(x) denotes the ball of radius r centered atx. Let ϕ _j,k ^(ɛ) (x)=2 ^nj2ϕ^(ɛ)(2 ^j x-k) be a wavelet basis forj ∈ ℤ, κ ∈ ℤⁿ, and ∈ ∈E, a finite set, and letP _j (T)=Σ_ɛ,k <T,ϕ _j,k ^(ɛ) >ϕ _j,k ^(ɛ) denote the associated projection operators at levelj (T is a suitable measure or distribution). Iff ∈Ls ^p(dμ) for 1 ≤p ≤ ∞, we show thatP _j(f dμ) ∈ L^p(dx) and ||P _j (fdμ)||L _p(dx)≤c2 ^{j((n-α)/p′))}||f||L _p(dμ) for allj ≥ 0. We also obtain estimates for the limsup and liminf of ||P _j (fdμ)||L _p(dx) under more restrictive hypotheses. Communicated by Guido Weiss     

Lower bounds at infinity of solutions of partial differential equations in the exterior of a proper cone

An extension of a classical theorem of Rellich to the exterior of a closed proper convex cone is proved: Let Γ be a closed convex proper cone inR ⁿ and −Γ′ be the antipodes of the dual cone of Γ. Let be a partial differential operator with constant coefficients inR ⁿ, whereQ(ζ)≠0 onR ⁿ−iΓ′ andP _i is an irreducible polynomial with real coefficients. Assume that the closure of each connected component of the set {ζ∈R ⁿ−iΓ′;P _j(ζ)=0, gradP _j(ζ)≠0} contains some real point on which gradP _j≠0 and gradP _j∉Γ∪(−Γ). LetC be an open cone inR ⁿ−Γ containing both normal directions at some such point, and intersecting each normal plane of every manifold contained in {ξ∈R ⁿ;P(ξ)=0}. Ifu∈ℒ′∩L _loc ² (R ⁿ−Γ) and the support ofP(−i∂/∂x)u is contained in Γ, then the condition implies that the support ofu is contained in Γ.     

Symmetric designs with bruck subdesigns

IfP is a finite projective plane of ordern with a proper subplaneQ of orderm which is not a Baer subplane, then a theorem of Bruck [Trans. AMS 78(1955), 464–481] asserts thatn≧m ²+m. If the equalityn=m ²+m were to occur thenP would be of composite order andQ should be called a Bruck subplane. It can be shown that if a projective planeP contains a Bruck subplaneQ, then in factP contains a designQ′ which has the parameters of the lines in a three dimensional projective geometry of orderm. A well known scheme of Bruck suggests using such aQ′ to constructP. Bruck’s theorem readily extends to symmetric designs [Kantor, Trans. AMS 146 (1969), 1–28], hence the concept of a Bruck subdesign. This paper develops the analoque ofQ′ and shows (by example) that the analogous construction scheme can be used to find symmetric designs.     

Inversion and characterization of the hemispherical transform

Explicit inversion formulas are obtained for the hemispherical transform(FΜ)(x) = Μ{y ∃S ⁿ :x. y ≥ 0},x ∃S ⁿ, whereS ⁿ is thendimensional unit sphere in ℝⁿ⁺¹,n ≥ 2, and Μ is a finite Borel measure onS ⁿ. If Μ is absolutely continuous with respect to Lebesgue measuredy onS ⁿ, i.e.,dΜ(y) =f(y)dy, we write(F f)(x) = ∫ _{x.y> 0} f(y)dy and consider the following cases: (a)f ∃C ^∞(Sⁿ); (b)f ∃ L^p(S ⁿ), 1 ≤ p < ∞; and (c)f ∃C(Sⁿ). In the case (a), our inversion formulas involve a certain polynomial of the Laplace-Beltrami operator. In the remaining cases, the relevant wavelet transforms are employed. The range ofF is characterized and the action in the scale of Sobolev spacesL _p ^γ (Sⁿ) is studied. For zonalf ∃ L¹(S ²), the hemispherical transformF f was inverted explicitly by P. Funk (1916); we reproduce his argument in higher dimensions. Partially sponsored by the Edmund Landau Center for Research in Mathematical Analysis, supported by the Minerva Foundation (Germany).     

L P boundedness of area function associated with operators on product spaces

Let L be the infinitesimal generator of an analytic semigroup on L2 (Rn) with suitable upper bounds on its heat kernels. Assume that L has a bounded holomorphic functional calculus on L2(Rn). In this paper,we define the Littlewood- Paley g function associated with L on Rn × Rn, denoted by GL(f)(x1, x2), and decomposition, we prove that ‖SL(f)‖p ≈‖GL(f)‖p ≈‖f‖p for 1 ＜ p ＜∞.     

On translation and dilation invariant subspaces of L p (ℝn), 0 < p < 1

We prove that each translation and dilation invariant subspace X ⊂ L ^p (ℝⁿ), X ≠ L ^p (ℝⁿ), is contained in a maximal translation and dilation invariant subspace of L ^p (ℝⁿ). Moreover, we prove that the set of all maximal translation and dilation invariant subspaces of L ^p (ℝⁿ) has the power of continuum. Bibliography: 6 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 345, 2007, pp. 5–21.     

Modified Cholesky algorithms: a catalog with new approaches

Given an n ×  n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A +  E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A +  E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of ||E||₂ =  O(n ²). An algorithm of Schnabel and Eskow further guarantees ||E||₂ =  O(n). We present variants that also ensure ||E||₂ =  O(n). Moré and Sorensen and Cheng and Higham used the block LBL ^T factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O(n ³) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL ^T -LBL ^T factorization, with T tridiagonal, that guarantees a modification cost of at most O(n ²). H.-r. Fang’s work was supported by National Science Foundation Grant CCF 0514213. D. P. O’Leary’s work was supported by National Science Foundation Grant CCF 0514213 and Department of Energy Grant DEFG0204ER25655.     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.