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.     

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 Note on Euclidean Ramsey Theory

Suppose n ≥ 2 and are such that X is infinite and Y is the set of vertices of an n-simplex. Then there is blue/red coloring of such that no set similar to X is monochromatically blue and no set similar to Y is monochromatically red.     

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.     

Banach-Mazur Distances and Projections on Random Subgaussian Polytopes

We consider polytopes in that are generated by N vectors in whose coordinates are independent subgaussian random variables. (A particular case of such polytopes are symmetric random polytopes generated by N independent vertices of the unit cube.) We show that for a random pair of such polytopes the Banach-Mazur distance between them is essentially of a maximal order n. This result is an analogue of the well-known Gluskin's result for spherical vectors. We also study the norms of projections on such polytopes and prove an analogue of Gluskin's and Szarek's results on basis constants. The proofs are based on a version of "small ball" estimates for linear images of random subgaussian vectors.     

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.     

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

Affine pseudo-planes with torus actions

An affine pseudo-plane X is a smooth affine surface defined over which is endowed with an -fibration such that every fiber is irreducible and only one fiber is a multiple fiber. If there is a hyperbolic -action on X and X is an -surface, we shall show that the universal covering is isomorphic to an affine hypersurface in the affine 3-space and X is the quotient of by the cyclic group via the action where and It is also shown that a -homology plane X with and a nontrivial -action is an affine pseudo-plane. The automorphism group is determined in the last section.     

Covering and packing in ${\Bbb Z}^n$ and ${\Bbb R}^n$, (I)

Given a finite subset of an additive group such as or , we are interested in efficient covering of by translates of , and efficient packing of translates of in . A set provides a covering if the translates with cover (i.e., their union is ), and the covering will be efficient if has small density in . On the other hand, a set will provide a packing if the translated sets with are mutually disjoint, and the packing is efficient if has large density. In the present part (I) we will derive some facts on these concepts when , and give estimates for the minimal covering densities and maximal packing densities of finite sets . In part (II) we will again deal with , and study the behaviour of such densities under linear transformations. In part (III) we will turn to . Authors’ address: Department of Mathematics, University of Colorado at Boulder, Campus Box 395, Boulder, Colorado 80309-0395, USA The first author was partially supported by NSF DMS 0074531.     

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 .     

Convolution Products in Naturally Ordered Semigroups

In this paper new equalities between two different convolution products in cancellative naturally ordered semigroups (but not in groups) are given. We also give several applications in particular cases and      

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

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 .     

Frame Decomposition of Decomposition Spaces

A new construction of tight frames for with flexible time-frequency localization is considered. The frames can be adapted to form atomic decompositions for a large family of smoothness spaces on a class of so-called decomposition spaces. The decomposition space norm can be completely characterized by a sparseness condition on the frame coefficients. As examples of the general construction, new tight frames yielding decompositions of Besov space, anisotropic Besov spaces, α-modulation spaces, and anisotropic α-modulation spaces are considered. Finally, curvelet-type tight frames are constructed on      

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.     

Smaller Coresets for k-Median and k-Means Clustering

In this paper we show that there exists a -coreset for k-median and k-means clustering of n points in which is of size independent of n. In particular, we construct a -coreset of size for k-median clustering, and of size for k-means clustering.     

Density of the Set of Generators of Wavelet Systems

Given a function ψ in the affine (wavelet) system generated by ψ, associated to an invertible matrix a and a lattice Γ, is the collection of functions In this paper we prove that the set of functions generating affine systems that are a Riesz basis of ${\cal L}^2({\Bbb R}^d)$ is dense in We also prove that a stronger result is true for affine systems that are a frame of In this case we show that the generators associated to a fixed but arbitrary dilation are a dense set. Furthermore, we analyze the orthogonal case in which we prove that the set of generators of orthogonal (not necessarily complete) affine systems, that are compactly supported in frequency, are dense in the unit sphere of with the induced metric. As a byproduct we introduce the p-Grammian of a function and prove a convergence result of this Grammian as a function of the lattice. This result gives insight in the problem of oversampling of affine systems.     

Local Growth Envelopes of Triebel-Lizorkin Spaces of Generalized Smoothness

The concept of local growth envelope of the quasi-normed function space is applied to the Triebel-Lizorkin spaces of generalized smoothness In order to achieve this, a standardization result for these and corresponding Besov spaces is derived.     

On the Least Median Square Problem

We consider the exact and approximate computational complexity of the multivariate least median-of-squares (LMS) linear regression estimator. The LMS estimator is among the most widely used robust linear statistical estimators. Given a set of n points in and a parameter k, the problem is equivalent to computing the narrowest slab bounded by two parallel hyperplanes that contains k of the points. We present algorithms for the exact and approximate versions of the multivariate LMS problem. We also provide nearly matching lower bounds for these problems. These lower bounds hold under the assumptions that k is Ω(n) and that deciding whether n given points in are affinely non-degenerate requires Ω(n^d) time.