Characterization of Planar Pseudo-Self-Similar Tilings

A pseudo-self-similar tiling is a hierarchical tiling of Euclidean space which obeys a nonexact substitution rule: the substitution for a tile is not geometrically similar to itself. An example is the Penrose tiling drawn with rhombi. We prove that a nonperiodic repetitive tiling of the plane is pseudo-self-similar if and only if it has a finite number of derived Vorono\"{\i} tilings up to similarity. To establish this characterization, we settle (in the planar case) a conjecture of E. A. Robinson by providing an algorithm which converts any pseudo-self-similar tiling of R ² into a self-similar tiling of R ² in such a way that the translation dynamics associated to the two tilings are topologically conjugate. Received June 20, 2000, and in revised form January 25, 2001. Online publication July 25, 2001.     

Maintaining the Extent of a Moving Point Set

Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of S . If the points in S move with algebraic motions, these structures process O(n ^2+\eps ) events. We also give constructions showing that Ω(n ² ) combinatorial changes are possible for these extent functions even if each point is moving with constant velocity. We give a similar construction and upper bound for the convex hull, improving known results. Received April 25, 2000, and in revised form September 25, 2000. Online publication May 4, 2001.     

Helly-Type Theorems on the Homology of the Space of Transversals

In this paper we ``measure' the size of the set of n -transversals of a family F of convex sets in R <sup>n+k</sup> according to its homological complexity inside the corresponding Grassmannian manifold. Our main result states that the ``measure' μ of the set of n -transversals of F is greater than or equal to k if and only if every k+1 members of F have a common point and also if and only if for some integer m , 1≤ m≤ n , and every subfamily F ^\prime of F with k+2 members, the ``measure' μ of the set of m -transversals of F ^\prime is greater than or equal to k . Received October 25, 2000, and in revised form September 27, 2001, and October 17, 2001. Online publication March 1, 2002.     

The cup product of Hilbert schemes for K3 surfaces

To any graded Frobenius algebra A we associate a sequence of graded Frobenius algebras A ^[n] so that there is canonical isomorphism of rings (H ^*(X;ℚ)[2]) ^[n] ≅H ^*(X ^[n] ;ℚ)[2n] for the Hilbert scheme X ^[n] of generalised n-tuples of any smooth projective surface X with numerically trivial canonical bundle. Oblatum 25-I-2001 & 18-IX-2002?Published online: 24 February 2003     

The Dirichlet problem at infinity for harmonic map equations arising from constant mean curvature surfaces in the hyperbolic 3-space

The purpose of this paper is to study some uniqueness, existence and regularity properties of the Dirichlet problem at infinity for proper harmonic maps from the hyperbolic m-space to the open unit n-ball with a specific incomplete metric. When m=n=2, harmonic solutions of this Dirichlet problem yield complete constant mean curvature surfaces in the hyperbolic 3-space. Received: 25 January 2001 / Accepted: 23 February 2001 / Published online: 25 June 2001     

A characterization of bielliptic curves and applications to their moduli spaces

We deal with the covers of degree 4 naturally associated to a bielliptic curve of genus g≥6, giving a proof of the unirationality of the moduli space ? _g ^be of such curves, of the rationality of the Hurwitz scheme ℌ ^be _{4, g} of bielliptic curves of even genus g, whereas, when g is odd, we construct a finite map ℂ^{2 g -2}→? _g ^be and compute its degree. Received: March 25, 2000; in final form: March 10, 2001?Published online: May 29, 2002     

Hankel and Toeplitz Transforms on H 1: Continuity, Compactness and Fredholm Properties

We revisit the boundedness of Hankel and Toeplitz operators acting on the Hardy space H ¹ and give a new proof of the old result stating that the Hankel operator H _a is bounded if and only if a has bounded logarithmic mean oscillation. We also establish a sufficient and necessary condition for H _a to be compact on H ¹. The Fredholm properties of Toeplitz operators on H ¹ are studied for symbols in a Banach algebra similar to C + H ^∞ under mild additional conditions caused by the differences in the boundedness of Toeplitz operators acting on H ¹ and H ². The first author was partially supported by the European Commission IHP Network “Harmonic Analysis and Related Problems” (Contract Number: HPRN-CT-2001-00273-HARP) and by the Greek Research Program “Pythagoras 2” (75% European funds and 25 National funds). The second author was fully supported by the European Commission IHP Network “Harmonic Analysis and Related Problems” (Contract Number: HPRN-CT-2001-00273-HARP) while he visited the first author at the University of Crete and later by the Academy of Finland Project 207048.     

A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability, the new matching satisfies that linear inequality in an approximate sense. This extends the well-known LP rounding procedure of Raghavan and Thompson, which is usually used to round fractional solutions of linear programs.?We use our rounding procedure to design an additive approximation algorithm to the Quadratic Assignment Problem. The approximation error of the algorithm is εn ² and it runs in n ^{O (log n /ε2)} time.?We also describe Polynomial Time Approximation Schemes (PTASs) for dense subcases of many well-known NP-hard arrangement problems, including MINIMUM LINEAR ARRANGEMENT, MINIMUM CUT LINEAR ARRANGEMENT, MAXIMUM ACYCLIC SUBGRAPH, and BETWEENNESS. Received: December 12, 1999 / Accepted: October 25, 2001?Published online February 14, 2002     

Post-Coulombian Dynamics at Order c-3

Summary. We study the dynamics of N charges interacting with the Maxwell field. If their initial velocities are small compared to the velocity of light, c , then in lowest order their motion is governed by the static Coulomb Lagrangian. We investigate higher-order corrections with an explicit control on the error terms. The Darwin correction, order |v/c| ² , has been proved previously. In this contribution we obtain the dissipative corrections due to radiation damping, which are of order |v/c| ³ relative to the Coulomb dynamics. If all particles have the same charge-to-mass ratio, the dissipation would vanish at that order. Received February 7, 2001; accepted September 21, 2001 Online publication November 30, 2001     

Real Hypersurfaces with Isometric Reeb Flow in Complex Two-Plane Grassmannians

 We classify all real hypersurfaces with isometric Reeb flow in the complex Grassmann manifold G ₂ (ℂ ^m+2 ) of all 2-dimensional linear subspaces in ℂ ^m+2 , m ≥ 3. The second author was supported by Korea Research Foundation. KRF-2001-015-DP0034, Korea. Received April 26, 2001; in revised form December 17, 2001     

Complete space-like hypersurfaces with constant scalar curvature

Let M ⁿ be a complete space-like hypersurface with constant normalized scalar curvature R in the de Sitter space S ^{n + 1} ₁ and denote . We prove that if the norm square of the second fundamental form of M ⁿ satisfies , then either and M ⁿ is a totally umbilical hypersurface; or , and, up to rigid motion, M ⁿ is a hyperbolic cylinder . Received: 8 February 2001 / Revised version: 27 April 2001     

Kähler hyperbolicity and the Euler number of a compact manifold with geodesic flow of Anosov type

 Let M be a 2m-dimensional compact Riemannian manifold with Anosov geodesic flow. We prove that every closed bounded k form, k≥2, on the universal covering of M is d(bounded). Further, if M is homotopy equivalent to a compact K?hler manifold, then its Euler number χ(M) satisfies (−1) ^m χ(M)>0. Received: 25 September 2001 / Published Online: 16 October 2002     

Bouquet and join theorems for disentanglements

The disentanglement of certain augmentations is shown to be the topological join of a disentanglement and a Milnor fibre. The kth disentanglement of a finite map is defined and for corank 1 maps from ℂ ⁿ to ℂ ^{n +1} it is shown that they are homotopically equivalent to a wedge of spheres. Applications to the Mond conjecture are given. Oblatum 24-VII-2000 & 5-VII-2001?Published online: 12 October 2001     

Global dynamics of approximate solutions to an age-structured epidemic model with diffusion

We consider an age-dependent s-i-s epidemic model with diffusion whose mortality is unbounded. We approximate the solution using Galerkin methods in the space variable combined with backward Euler along the characteristic direction in the age and time variables. It is proven that the scheme is stable and convergent in optimal rate in l ^∞,2 (L ²) norm. To investigate the global behavior of the discrete solution resulting from the algorithm, we reformulate the resulting system into a monotone form. Positivity of the nonlocal birth process is proved using the positivity of the first eigenvalue of the resulting matrix system and using the fact that the positivity is preserved along the characteristics. The difference equation of the steady state coupled with nonlocal birth process is solved by developing monotone iterative schemes. The stability of the discrete solution of the steady state is then analyzed by constructing suitable positive subsolutions. Mathematics subject classifications (2000) 65M12, 65M25, 65M60, 92D25 M.-Y. Kim: This work was supported by Korea Research Foundation Grant (KRF-2001-041-D00037).     

Exact and Approximation Algorithms for Minimum-Width Cylindrical Shells

Let S be a set of n points in \reals ³ . Let \opt be the width (i.e., thickness) of a minimum-width infinite cylindrical shell (the region between two co-axial cylinders) containing S . We first present an O(n ⁵ ) -time algorithm for computing \opt , which as far as we know is the first nontrivial algorithm for this problem. We then present an O(n ^2+δ ) -time algorithm, for any δ>0 , that computes a cylindrical shell of width at most 56\opt containing S . Received May 31, 2000, and in revised form October 25, 2000. Online publication August 29, 2001.     

Non-crossed products over function fields

Noncrossed product division algebras are constructed over all function fields and iterated power series fields over global fields, using Hilbert's Irreducibility Theorem and the construction of [B]. Minimum indexes obtained are p ² for odd p and 2³ otherwise. Examples are obtained with large index to exponent ratio. Received: 12 February 2001 / Revised version: 26 November 2001     

Feuilletages holomorphes locaux et analyticité partielle d'applications C ∞

 Let f : M → M′ be a smooth CR mapping between a generic real analytic submanifold M ⊂ ℂ ⁿ , n > 1, and a real analytic subset M′ ⊂ ℂ ^n′ . We prove that if M is minimal and if M′ does not contain any complex curves, then f is analytic on a dense open subset of M. More generally, we establish an upper estimate of the partial analyticity of f, which depends on the maximal dimension of local holomorphic foliations contained in M ^′ . Received: 7 August 2001 Mathematics Subject Classification (2000): 32V25, 32V40, 32H99     

A Tight Bound on the Number of Geometric Permutations of Convex Fat Objects in R d

We show that the maximum number of geometric permutations of a set of n pairwise-disjoint convex and fat objects in R ^d is O(n ^d-1 ) . This generalizes the bound of Θ (n ^d-1 ) obtained by Smorodinsky et al. [5] on the number of geometric permutations of n pairwise-disjoint balls. Received August 22, 2000, and in revised form February 6, 2001. Online publication October 12, 2001.     

Estimates for the Scattering Map Associated with a Two-Dimensional First-Order System

Summary. We consider the scattering transform for the first-order system in the plane, We show that the scattering map is Lipschitz continuous on a neighborhood of zero in L ² . Received September 11, 2000; accepted August 27, 2001 Online publication November 5, 2001     

An Optimal Deterministic Algorithm for Computing the Diameter of a Three-Dimensional Point Set

We describe a deterministic algorithm for computing the diameter of a finite set of points in R ³ , that is, the maximum distance between any pair of points in the set. The algorithm runs in optimal time O(nlog n) for a set of n points. The first optimal, but randomized, algorithm for this problem was proposed more than 10 years ago by Clarkson and Shor [11] in their ground-breaking paper on geometric applications of random sampling. Our algorithm is relatively simple except for a procedure by Matoušek [25] for the efficient deterministic construction of epsilon-nets. This work improves previous deterministic algorithms by Ramos [31] and Bespamyatnikh [7], both with running time O(nlog ² n) . The diameter algorithm appears to be the last one in Clarkson and Shor's paper that up to now had no deterministic counterpart with a matching running time. Received May 10, 2000, and in revised form November 3, 2000. Online publication June 22, 2001.