A method for exact calculation of the discrepancy of low-dimensional finite point sets I

In the present paper the formulas of exactly calculating the discrepancy of 2-and 3-dimensional finite point sets are explicitly given only in terms of the components of points.     

On the length of longest alternating paths for multicoloured point sets in convex position

Let P be a set of points in R² in general position such that each point is coloured with one of k colours. An alternating path of P is a simple polygonal whose edges are straight line segments joining pairs of elements of P with different colours. In this paper we prove the following: suppose that each colour class has cardinality s and P is the set of vertices of a convex polygon. Then P always has an alternating path with at least (k-1)s elements. Our bound is asymptotically sharp for odd values of k.     

Empty pseudo-triangles in point sets

We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n²) and Θ(n³) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n³) and Θ(n⁶). If we count only star-shaped pseudo-triangles, the bounds are Θ(n²) and Θ(n⁵). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n³) time. In the general case, the running times are O(n⁶) for the maximization problems and O(nlogn) for the minimization problems.     

On the finite integral transform method for exact bending solutions of fully clamped orthotropic rectangular thin plates

Exact bending solutions of fully clamped orthotropic rectangular thin plates subjected to arbitrary loads are derived using the finite integral transform method. In the proposed mathematical method one does not need to predetermine the deformation function because only the basic governing equations of the classical plate theory for orthotropic plates are used in the procedure. Therefore, unlike conventional semi-inverse methods, it serves as a completely rational and accurate model in plate bending analysis. The applicability of the method is extensive, and it can handle plates with different loadings in a uniform procedure, which is simpler than previous methods. Numerical results are presented to demonstrate the validity and accuracy of the approach as compared with those previously reported in the bibliography.     

A thorough analysis of the discrepancy of shifted Hammersley and van der Corput point sets

We study the star discrepancy of Hammersley nets and van der Corput sequences which are important examples of low-dimensional quasi-Monte Carlo point sets. By a so-called digital shift, the quality of distribution of these point sets can be improved. In this paper, we advance and extend existing bounds on digitally shifted Hammersley and van der Corput point sets and establish criteria for the choice of digital shifts leading to optimal results. Our investigations are partly based on a close analysis of certain sums of distances to the nearest integer. Mathematics Subject Classi cation (2000) 11K38; 11K09     

A hierarchy of hereditarily finite sets

This article defines a hierarchy on the hereditarily finite sets which reflects the way sets are built up from the empty set by repeated adjunction, the addition to an already existing set of a single new element drawn from the already existing sets. The structure of the lowest levels of this hierarchy is examined, and some results are obtained about the cardinalities of levels of the hierarchy.      

A note on fixed point sets in CAT(0) spaces

We show that the fixed point set of a quasi-nonexpansive selfmap of a nonempty convex subset of a CAT(0) space is always closed, convex and contractible. Moreover, we give a construction of a continuous selfmap of a CAT(0) space whose fixed point set is prescribed.     

Lp- and Sp,qrB-discrepancy of the symmetrized van der Corput sequence and modified Hammersley point sets in arbitrary bases

We study the local discrepancy of a symmetrized version of the well-known van der Corput sequence and of modified two-dimensional Hammersley point sets in arbitrary base $b$. We give upper bounds on the norm of the local discrepancy in Besov spaces of dominating mixed smoothness $S_{p,q}^{r}B\left({[0,1)}^s\right)$, which will also give us bounds on the $L_p$-discrepancy. Our sequence and point sets will achieve the known optimal order for the $L_p$- and $S_{p,q}^{r}B$-discrepancy. The results in this paper generalize several previous results on $L_p$- and $S_{p,q}^{r}B$-discrepancy estimates and provide a sharp upper bound on the $S_{p,q}^{r}B$-discrepancy of one-dimensional sequences for $r>0$. We will use the $b$-adic Haar function system in the proofs.     

Universal point sets for planar three-trees

For every $n\in \mathbb{N}$, we present a set $S_n$ of $O(n^{3/2}\log n)$ points in the plane such that every planar 3-tree with n vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of $S_n$. This is the first subquadratic upper bound on the cardinality of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs.     

On the discrepancy of random low degree set systems

Motivated by the celebrated Beck‐Fiala conjecture, we consider the random setting where there are n elements and m sets and each element lies in t randomly chosen sets. In this setting, Ezra and Lovett showed an discrepancy bound when n ≤ m and an O(1) bound when n ? m^t. In this paper, we give a tight bound for the entire range of n and m, under a mild assumption that . The result is based on two steps. First, applying the partial coloring method to the case when and using the properties of the random set system we show that the overall discrepancy incurred is at most . Second, we reduce the general case to that of using LP duality and a careful counting argument.     

Integral point sets in higher dimensional affine spaces over finite fields

We consider point sets in the m-dimensional affine space where each squared Euclidean distance of two points is a square in Fq. It turns out that the situation in is rather similar to the one of integral distances in Euclidean spaces. Therefore we expect the results over finite fields to be useful for the Euclidean case.We completely determine the automorphism group of these spaces which preserves integral distances. For some small parameters m and q we determine the maximum cardinality I(m,q) of integral point sets in . We provide upper bounds and lower bounds on I(m,q). If we map integral distances to edges in a graph, we can define a graph Gm,q with vertex set . It turns out that Gm,q is strongly regular for some cases.     

Error estimates for the finite point method

In this paper, error estimates for the finite point method are presented in Sobolev spaces in multiple dimensions when nodes and shape functions satisfy certain conditions. From the error analysis of the finite point method, the error bound of the numerical solution is directly related to the radii of the weight functions and the condition number of the coefficient matrix.     

Absolute fixed point sets for continuum-valued maps

The notion of an absolute fixed point set in the setting of continuum-valued maps will be defined and characterized.

     

A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley

A method is given to calculate exactly the stardiscrepancy of arbitrary finite plane sets. Using this method the stardiscrepancy of the sequences of Hammersley is obtained. The recursive structure of these sets allows for a proof by induction.     

Absolute fixed point sets for multi-valued maps

The notion of a multi-valued absolute fixed point set (MAFS) will be defined and characterized in the setting of set-valued maps with images containing multiple components.