Line Transversals to Translates of Unit Discs

Let be a family of convex figures in the plane. We say that has property T if there exists a line intersecting every member of . Also, the family has property T(k) if every k-membered subfamily of has property T. Let B be the unit disc centered at the origin. In this paper we prove that if a finite family of translates of B has property T(4) then the family , where , has property T. We also give some results concerning families of translates of the unit disc which has either property T(3) or property T(5).     

Coefficients of Orthogonal Polynomials on the Unit Circle and Higher-Order Szego Theorems

Let be a nontrivial probability measure on the unit circle the density of its absolutely continuous part, its Verblunsky coefficients, and its monic orthogonal polynomials. In this paper we compute the coefficients of in terms of the . If the function is in , we do the same for its Fourier coefficients. As an application we prove that if and if is a polynomial, then with and S the left-shift operator on sequences we have

On Distinct Distances from a Vertex of a Convex Polygon

Given a set P of n points in convex position in the plane, we prove that there exists a point such that the number of distinct distances from p is at least The best previous bound, from 1952, is due to Moser.     

Staircase Connected Sets

A compact set is staircase connected if every two points can be connected by a polygonal path with sides parallel to the coordinate axes, which is both x-monotone and y-monotone. denotes the smallest number of edges of such a path. is an integer-valued metric on S. We investigate this metric and introduce stars and kernels. Our main result is that the r-th kernel is nonempty, compact and staircase connected provided .     

Improved Approximation Algorithms for Geometric Set Cover

Given a collection S of subsets of some set and the set cover problem is to find the smallest subcollection that covers that is, where denotes We assume of course that S covers While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually Combining previously known techniques [4], [5], we show that polynomial-time approximation algorithms with provable performance exist, under a certain general condition: that for a random subset and nondecreasing function f(·), there is a decomposition of the complement into an expected at most f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|)) can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudo-disks, by a family of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects, and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in and for guarding an x-monotone polygonal chain.     

Covering a Triangle with Positive and Negative Homothetic Copies

Let be a triangle and let be a set of homothetic copies of . We prove that implies that there are positive and negative signs and there exist translates of that cover .     

Ideals of Ultrafilters on the Collection of Finite Subsets of an Infinite Set

Let J be an infinite set and let , i.e., I is the collection of all non empty finite subsets of J. Let denote the collection of all ultrafilters on the set I and let be the compact (Hausdorff) right topological semigroup that is the Stone-Cech Compactification of the semigroup equipped with the discrete topology. This paper continues the study of that was started in [3] and [5]. In [5], Koppelberg established that (where K( S) is the smallest ideal of a semigroup S) and for non empty she established . In this note, we show that for such that is infinite, is a proper subset of and , where .     

Kernel and Trace Operators for Extensions of Brandt Semigroups

Let S be an (ideal) extension of a Brandt semigroup S₀ by a Brandt semigroup S₁ and let denote the congruence lattice of S. For denote by and the least and the greatest congruences on S with the same kernel as respectively, and let and have the analogous meaning relative to trace. We establish necessary and sufficient conditions on S in order that one or more of the operators

A Single Cell in an Arrangement of Convex Polyhedra in ${\Bbb R}^3$

We show that the combinatorial complexity of a single cell in an arrangement of k convex polyhedra in 3-space having n facets in total is , for any , thus settling a conjecture of Aronov et al. We then extend our analysis and show that the overall complexity of the zone of a low-degree algebraic surface, or of the boundary of an arbitrary convex set, in an arrangement of k convex polyhedra in 3-space with n facets in total, is also , for any . Finally, we present a deterministic algorithm that constructs a single cell in an arrangement of this kind, in time , for any .     

Numerical Integration over Spheres of Arbitrary Dimension

In this paper we study the worst-case error (of numerical integration) on the unit sphere for all functions in the unit ball of the Sobolev space where More precisely, we consider infinite sequences of m(n)-point numerical integration rules where: (i) is exact for all spherical polynomials of degree and (ii) has positive weights or, alternatively to (ii), the sequence satisfies a certain local regularity property. Then we show that the worst-case error (of numerical integration) in has the upper bound where the constant c depends on s and d (and possibly the sequence This extends the recent results for the sphere by K. Hesse and I.H. Sloan to spheres of arbitrary dimension by using an alternative representation of the worst-case error. If the sequence of numerical integration rules satisfies an order-optimal rate of convergence is achieved.     

A Two-Dimensional Kinetic Triangulation with Near-Quadratic Topological Changes

A triangulation of a set S of points in the plane is a subdivision of the convex hull of S into triangles whose vertices are points of S. Given a set S of n points in each moving independently, we wish to maintain a triangulation of S. The triangulation needs to be updated periodically as the points in S move, so the goal is to maintain a triangulation with a small number of topological events, each being the insertion or deletion of an edge. We propose a kinetic data structure (KDS) that processes topological events with high probability if the trajectories of input points are algebraic curves of fixed degree. Each topological event can be processed in time. This is the first known KDS for maintaining a triangulation that processes a near-quadratic number of topological events, and almost matches the lower bound [1]. The number of topological events can be reduced to if only k of the points are moving.     

Distributional Point Values and Convergence of Fourier Series and Integrals

In this article we show that the distributional point values of a tempered distribution are characterized by their Fourier transforms in the following way: If and , and is locally integrable, then distributionally if and only if there exists k such that , for each a > 0, and similarly in the case when is a general distribution. Here means in the Cesaro sense. This result generalizes the characterization of Fourier series of distributions with a distributional point value given in [5] by . We also show that under some extra conditions, as if the sequence belongs to the space for some and the tails satisfy the estimate ,\ as , the asymmetric partial sums\ converge to . We give convergence results in other cases and we also consider the convergence of the asymmetric partial integrals. We apply these results to lacunary Fourier series of distributions.     

Hardy Spaces for Laguerre Expansions

Let be the standard Laguerre functions of type a. We denote . Let and be the semigroups associated with the orthonormal systems and . We say that a function f belongs to the Hardy space associated with one of the semigroups if the corresponding maximal function belongs to . We prove special atomic decompositions of the elements of the Hardy spaces.     

Row Space Cardinalities

Let be the set of all Boolean matrices. Let R(A) denote the row space of , let , and let . By extensive computation we found that

The Uniqueness of Shift-Generated Duals for Frames in Shift-Invariant Subspaces

Given an invertible matrix B and a finite or countable subset of , we consider the collection generating the closed subspace of . If that collection forms a frame for , one can introduce two different types of shift-generated (SG) dual frames for X, called type I and type II SG-duals, respectively. The main distinction between them is that a SG-dual of type I is required to be contained in the space generated by the original frame while, for a type II SG-dual, one imposes that the range of the frame transform associated with the dual be contained in the range of the frame transform associated with the original frame. We characterize the uniqueness of both types of duals using the Gramian and dual Gramian operators which were introduced in an article by Ron and Shen and are known to play an important role in the theory of shift-invariant spaces.     

Spherical Perturbations of Schrödinger Equations

We give conditions on radial nonnegative weights $W_1We give conditions on radial nonnegative weights and on , for which the a priori inequality holds with constant independent of . Here is the Laplace-Beltrami operator on the sphere . Due to the relation between and the tangential component of the gradient, , we obtain some "Morawetz-type" estimates for on . As a consequence we establish some new estimates for the free Schr?dinger propagator , which may be viewed as certain refinements of the -(super)smoothness estimates of Kato and Yajima. These results, in turn, lead to the well-posedness of the initial value problem for certain time dependent first order spherical perturbations of the dimensional Schr?dinger equation.     

Quantitative Robust Uncertainty Principles and Optimally Sparse Decompositions

In this paper we develop a robust uncertainty principle for finite signals in which states that, for nearly all choices such that

The Entropy in Learning Theory. Error Estimates

We continue the investigation of some problems in learning theory in the setting formulated by F. Cucker and S. Smale. The goal is to find an estimator on the base of given data that approximates well the regression function of an unknown Borel probability measure defined on We assume that belongs to a function class It is known from previous works that the behavior of the entropy numbers of in the uniform norm plays an important role in the above problem. The standard way of measuring the error between a target function and an estimator is to use the norm ( is the marginal probability measure on X generated by ). This method has been used in previous papers. We continue to use this method in this paper. The use of the norm in measuring the error has motivated us to study the case when we make an assumption on the entropy numbers of in the norm. This is the main new ingredient of thispaper. We construct good estimators in different settings: (1) we know both and ; (2) we know but we do not know and (3) we only know that is from a known collection of classes but we do not know An estimator from the third setting is called a universal estimator.     

Isometry-Invariant Valuations on Hyperbolic Space

Hyperbolic area is characterized as the unique continuous isometry-invariant simple valuation on convex polygons in We then show that continuous isometry-invariant simple valuations on polytopes in for are determined uniquely by their values at ideal simplices. The proofs exploit a connection between valuation theory in hyperbolic space and an analogous theory on the Euclidean sphere. These results lead to characterizations of continuous isometry-invariant valuations on convex polytopes and convex bodies in the hyperbolic plane a partial characterization in and a mechanism for deriving many fundamental theorems of hyperbolic integral geometry, including kinematic formulas, containment theorems, and isoperimetric and Bonnesen-type inequalities.     

A Lattice of Quasivarieties of Normal Cryptogroups

A normal cryptogroup S is a completely regular semigroup in which is a congruence and is a normal band. We represent S as a strong semilattice of completely simple semigroups, and may set For each we set and represent by means of an h-quintuple These parameters are used to characterize certain quasivarieties of normal cryptogroups. Specifically, we construct the lattice of quasivarieties generated by the (quasi)varieties and This is the lattice generated by the lattice of quasivarieties of normal bands, groups and completely simple semigroups. We also determine the B-relation on the lattice of all quasivarieties of normal cryptogroups. Each quasivariety studied is characterized in several ways.