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.     

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.     

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.     

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.     

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.     

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.     

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.     

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）.