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 .     

Monoids and Cuspidal Group Characters

Let M be a finite monoid with unit group G. By the work of Munn and Ponizovski, the irreducible complex representations of M are classified according to which J-class (apex) they come from. Consider the irreducible representations of M with apex . These representations restrict to representations of G, whose components we view as coming from J-classes below G. The remaining irreducible representations (and their characters) of G are called cuspidal. We show that an irreducible character of G is cuspidal if and only if for all idempotents , where .     

Invariance Theorems in Approximation Theory and their Applications

Let B be a closed linear subspace of a Banach space F and let be a group of continuous linear operators , where G is a compact topological group. We prove that if is invariant under , then under some conditions on f, F, B, and G, there exists an element of best approximation to f that has the same property. As applications, we compute the bivariate Bernstein constant for polynomial approximation of and solve a Braess problem on the exponential order of decay of the error of polynomial approximation of . Other examples and applications are discussed as well.     

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.     

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

Orthogonal Algebraic Polynomial Schauder Bases of Optimal Degree

For any fixed we construct an orthonormal Schauder basis for C[-1,1] consisting of algebraic polynomials with The orthogonality is with respect to the Chebyshev weight.     

Asymptotics of Laurent Polynomials of Odd Degree Orthogonal with Respect to Varying Exponential Weights

Let denote the linear space over spanned by . Define the (real) inner product , where V satisfies: (i) V is real analytic on ; (ii) ; and (iii) . Orthogonalisation of the (ordered) base with respect to yields the even degree and odd degree orthonormal Laurent polynomials , and . Define the even degree and odd degree monic orthogonal Laurent polynomials: and . Asymptotics in the double-scaling limit such that of (in the entire complex plane), , and (in the entire complex plane) are obtained by formulating the odd degree monic orthogonal Laurent polynomial problem as a matrix Riemann-Hilbert problem on , and then extracting the large-n behaviour by applying the non-linear steepest-descent method introduced in [1] and further developed in [2],[3].     

Generating Self-Map Monoids of Infinite Sets

Let be a countably infinite set, the group of permutations of , and the monoid of self-maps of . Given two subgroups , let us write if there exists a finite subset such that the groups generated by and are equal. Bergman and Shelah showed that the subgroups which are closed in the function topology on S fall into exactly four equivalence classes with respect to . Letting denote the obvious analog of for submonoids of E, we prove an analogous result for a certain class of submonoids of E, from which the theorem for groups can be recovered. Along the way, we show that given two subgroups which are closed in the function topology on S, we have if and only if (as submonoids of E), and that for every subgroup (where denotes the closure of G in the function topology in S and its closure in the function topology in E).     

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

Multiresolution Analysis and Multivariate Approximation of Smooth Signals in CB(Rd

In this paper we derive rates of approximation for a class of linear operators on associated with a multiresolution analysis We show that for a uniformly bounded sequence of linear operators satisfying on the subspace a lower bound for the approximation order is determined by the number of vanishing moments of a prewavelet set. We consider applications to extensions of generalized projection operators as well as to sampling series.     

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 .     

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

Direct Sum Decomposition of L2(Rn 1) into Subspaces Invariant under Fourier Transformation

Denote by the real-linear span of , where Under the concept of left-monogeneity defined through the generalized Cauchy-Riemann operator we obtain the direct sum decomposition of

Localized Polynomial Frames on the Ball

Almost exponentially localized polynomial kernels are constructed on the unit ball in with weights , by smoothing out the coefficients of the corresponding orthogonal projectors. These kernels are utilized to the design of cubature formulas on with respect to and to the construction of polynomial tight frames in (called needlets) whose elements have nearly exponential localization.     

Distinct Distances in Homogeneous Sets in Euclidean Space

It is shown that every homogeneous set of n points in d-dimensional Euclidean space determines at least distinct distances for a constant c(d) > 0. In three-space the above general bound is slightly improved and it is shown that every homogeneous set of n points determines at least distinct distances.     

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.     

Plane Embeddings of Planar Graph Metrics

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires distortion in the worst case [M1], [BMMV], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matousek [M3] by proving that some planar graph metrics require distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.     

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.     

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 .     

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.