Point sets with low <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-discrepancy

In this paper we study the L _p -discrepancy of digitally shifted Hammersley point sets. While it is known that the (unshifted) Hammersley point set (which is also known as Roth net) with N points has L _p -discrepancy (p an integer) of order (log N)/N, we show that there always exists a shift such that the digitally shifted Hammersley point set has L _p -discrepancy (p an even integer) of order which is best possible by a result of W. Schmidt. Further we concentrate on the case p = 2. We give very tight lower and upper bounds for the L ₂-discrepancy of digitally shifted Hammersley point sets which show that the value of the L ₂-discrepancy of such a point set mostly depends on the number of zero coordinates of the shift and not so much on the position of these. This work is supported by the Austrian Research Fund (FWF), Project P17022-N12 and Project S8305.     

Computing Discrepancies of Smolyak Quadrature Rules

In recent years, Smolyak quadrature rules (also called quadratures on hyperbolic cross points or sparse grids) have gained interest as possible competition to number theoretic quadratures for high dimensional problems. A standard way of comparing the quality of multivariate quadrature formulas consists in computing theirL₂-discrepancy. Especially for larger dimensions, such computations are a highly complex task. In this paper we develop a fast recursive algorithm for computing theL₂-discrepancy (and related quality measures) of general Smolyak quadratures. We carry out numerical comparisons between the discrepancies of certain Smolyak rules and Hammersley and Monte Carlo sequences.     

Walsh Series Analysis of the L 2-Discrepancyof Symmetrisized Point Sets

 We present a method to estimate the L ₂-discrepancy of symmetrisized point sets from above and from below with the help of Walsh series analysis. We apply the method to a class of two-dimensional net-type point sets, thereby generalizing results of Halton and Zaremba and of Proinov.     

Zur Konvergenz derL n -Diskrepanz gegen die extreme Diskrepanz

This paper gives bounds for the rate of convergence of theL _n -discrepancy of a sequence of points of thes-dimensional space ^s (s. Further, a formula to calculate theL _n -discrepancy for even numbersn is given.     

Walsh Series Analysis of the L 2-Discrepancyof Symmetrisized Point Sets

 We present a method to estimate the L ₂-discrepancy of symmetrisized point sets from above and from below with the help of Walsh series analysis. We apply the method to a class of two-dimensional net-type point sets, thereby generalizing results of Halton and Zaremba and of Proinov. (Received 14 September 2000)     

On the -Discrepancy of the Hammersley Point Set

 We give a formula for the -discrepancy of the 2-dimensional Hammersley point set in base 2 for all integers p, .     

Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces

We extend the notion of L₂-B-discrepancy introduced in [E. Novak, H. Wo?niakowski, L₂ discrepancy and multivariate integration, in: W.W.L. Chen, W.T. Gowers, H. Halberstam, W.M. Schmidt, and R.C. Vaughan (Eds.), Analytic Number Theory. Essays in Honour of Klaus Roth, Cambridge University Press, Cambridge, 2009, pp. 359-388] to what we shall call weighted geometric L₂-discrepancy. This extension enables us to consider weights in order to moderate the importance of different groups of variables, as well as to consider volume measures different from the Lebesgue measure and classes of test sets different from measurable subsets of Euclidean spaces.We relate the weighted geometric L₂-discrepancy to numerical integration defined over weighted reproducing kernel Hilbert spaces and settle in this way an open problem posed by Novak and Wo?niakowski.Furthermore, we prove an upper bound for the numerical integration error for cubature formulas that use admissible sample points. The set of admissible sample points may actually be a subset of the integration domain of measure zero. We illustrate that particularly in infinite-dimensional numerical integration it is crucial to distinguish between the whole integration domain and the set of those sample points that actually can be used by the algorithms.     

An asymptotic relation between the extreme discrepancy and theL p -discrepancy

An asymptotic expression for the difference between the extreme discrepancy and theL _p -discrepancy of a sequence of points in thes-dimensional unit cube (0, 1] ^s ,s1, is given.     

Algorithmic construction of low-discrepancy point sets via dependent randomized rounding

We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on recent results on randomized roundings respecting hard constraints and their derandomization. It is structurally much simpler than a previous algorithm presented for this problem in [B. Doerr, M. Gnewuch, A. Srivastav, Bounds and constructions for the star discrepancy via δ$\delta$-covers, J. Complexity, 21 (2005) 691–709]. Besides leading to better theoretical running time bounds, our approach also can be implemented with reasonable effort. We implemented this algorithm and performed numerical comparisons with other known low-discrepancy constructions. The experiments take place in dimensions ranging from 5 to 21 and indicate that our algorithm leads to superior results if the dimension is relatively high and the number of points that have to be constructed is rather small.     

On the -Discrepancy of the Hammersley Point Set

 We give a formula for the -discrepancy of the 2-dimensional Hammersley point set in base 2 for all integers p, . Received 18 May 2001; in revised form 18 December 2001     

Wrap-Around L2-Discrepancy of Random Sampling, Latin Hypercube and Uniform Designs

For comparing random designs and Latin hypercube designs, this paper con- siders a wrap-around version of the L₂-discrepancy (WD). The theoretical expectation and variance of this discrepancy are derived for these two designs. The expectation and variance of Latin hypercube designs are significantly lower than those of the corresponding random designs. We also study construction of the uniform design under the WD and show that one-dimensional uniform design under this discrepancy can be any set of equidistant points. For high dimensional uniform designs we apply the threshold accepting heuristic for finding low discrepancy designs. We also show that the conjecture proposed by K. T. Fang, D. K. J. Lin, P. Winker, and Y. Zhang (2000, Technometrics) is true under the WD when the design is complete.     

Dyadic Diaphony of Digital Nets Over ?2

The dyadic diaphony, introduced by Hellekalek and Leeb, is a quantitative measure for the irregularity of distribution of point sets in the unit-cube. In this paper we study the dyadic diaphony of digital nets over ℤ₂. We prove an upper bound for the dyadic diaphony of nets and show that the convergence order is best possible. This follows from a relation between the dyadic diaphony and the L₂{\cal L}_2 discrepancy. In order to investigate the case where the number of points is small compared to the dimension we introduce the limiting dyadic diaphony, which is defined as the limiting case where the dimension tends to infinity. We obtain a tight upper and lower bound and we compare this result with the limiting dyadic diaphony of a random sample.     

Diameter and radius in the Manhattan metric

We investigate maximum size sets of lattice points with a given diameter,d, within a given rectilinearly bounded finite regionR inn dimensions, under the Manhattan orL1 metric. We show that when the length ofR in each dimension is an odd integer (as, for example, then-cube) there is, for every integerd, a maximum size set having radiusd/2 about some center, though the center need not be a lattice point.Similar results are obtained whenR has even length in some dimensions, except for a set ofd values whose cardinality is one less than the number of dimensions in whichR has even length. This question is still open for these values.This research was supported in part by AF Grant OSR-86-0078 and NSF Grant DMS-86-06225.     

Centered -discrepancy of random sampling and Latin hypercube design, and construction of uniform designs

In this paper properties and construction of designs under a centered version of the -discrepancy are analyzed. The theoretic expectation and variance of this discrepancy are derived for random designs and Latin hypercube designs. The expectation and variance of Latin hypercube designs are significantly lower than that of random designs. While in dimension one the unique uniform design is also a set of equidistant points, low-discrepancy designs in higher dimension have to be generated by explicit optimization. Optimization is performed using the threshold accepting heuristic which produces low discrepancy designs compared to theoretic expectation and variance.

     

L p-discrepancy and statistical independence of sequences

We characterize statistical independence of sequences by the L ^p-discrepancy and the Wiener L ^p-discrepancy. Furthermore, we find asymptotic information on the distribution of the L ²-discrepancy of sequences     

Colorful Strips

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k − 1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k − 1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy.     

On the L2-Discrepancy of the Sobol–Hammersley Net in Dimension 3

With the help of Walsh series analysis we show that the symmetrized Sobol–Hammersley net in base 2 and dimension 3 has almost best possible order of L₂ -discrepancy.     

Two point sets with additional properties

A subset of the plane is called a two point set if it intersects any line in exactly two points. We give constructions of two point sets possessing some additional properties. Among these properties we consider: being a Hamel base, belonging to some σ-ideal, being (completely) nonmeasurable with respect to different σ-ideals, being a κ-covering. We also give examples of properties that are not satisfied by any two point set: being Luzin, Sierpiński and Bernstein set. We also consider natural generalizations of two point sets, namely: partial two point sets and n point sets for n = 3, 4, …, ?₀, ?₁. We obtain consistent results connecting partial two point sets and some combinatorial properties (e.g. being an m.a.d. family).     

Stability problems in a theorem of F. Schur

Schur's theorem states that an isotropic Riemannian manifold of dimension greater than two has constant curvature. It is natural to guess that compact almost isotropic Riemannian manifolds of dimension greater than two are close to spaces of almost constant curvature. We take the curvature anisotropy as the discrepancy of the sectional curvatures at a point. The main result of this paper is that Riemannian manifolds in Cheeger's class ℜ(n,d,V,A) withL ₁-small integral anisotropy haveL _p-small change of the sectional curvature over the manifold. We also estimate the deviation of the metric tensor from that of constant curvature in theW _p ² -norm, and prove that compact almost isotropic spaces inherit the differential structure of a space form. These stability results are based on the generalization of Schur' theorem to metric spaces.     

Intersecting self-similar Cantor sets

We define a self-similar set as the (unique) invariant set of an iterated function system of certain contracting affine functions. A topology on them is obtained (essentially) by inducing theC ¹-topology of the function space. We prove that the measure function is upper semi-continuous and give examples of discontinuities. We also show that the dimension is not upper semicontinuous. We exhibit a class of examples of self-similar sets of positive measure containing an open set. IfC ₁ andC ₂ are two self-similar setsC ₁ andC ₂ such that the sum of their dimensionsd(C ₁)+d(C ₂) is greater than one, it is known that the measure of the intersection setC ₂–C ₁ has positive measure for almost all self-similar sets. We prove that there are open sets of self-similar sets such thatC ₂–C ₁ has arbitrarily small measure.