Combinatorial methods in the construction of point sets with uniformity properties

It is well known that (t, m, s)-nets are useful in numerical analysis. Many of the constructions of such nets arise from number theoretic or algebraic constructions. Less well known is the fact that combinatorial constructions also yield nets with very good and in many cases, optimal parameters. In this paper, we provide a survey of such combinatorial constructions of (t, m, s)-nets.     

Low-discrepancy point sets

Various point sets in thes-dimensional unit cube with small discrepancy are constructed.Dedicated to Professor E. Hlawka on the occasion of his seventieth birthday     

Instability of discrete point sets]{Instability of discrete point sets

Summary Let <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"3"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"4"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"5"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"6"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"7"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"8"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"9"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"10"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"11"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>X$ be a discrete subset of Euclidean $d$-space. We allow subsequently continuous movements of single elements, whenever the minimum distance to other elements does not decrease. We discuss the question, if it is possible to move all elements of $X$ in this way, for example after removing a finite subset $Y$ from $X$. Although it is not possible in general, we show the existence of such finite subsets $Y$ for many discrete sets $X$, including all lattices. We define the \textit{instability degree} of $X$ as the minimum cardinality of such a subset $Y$ and show that the maximum instability degree among lattices is attained by perfect lattices. Moreover, we discuss the $3$-dimensional case in detail.     

Exact sampling with highly uniform point sets

In 1996, Propp and Wilson came up with a remarkably clever method for generating exact samples from the stationary distribution of a Markov chain [J.G. Propp, D.B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures and Algorithms 9 (1–2) (1996) 223–252]. Their method, called “perfect sampling” or “exact sampling” avoids the inherent bias of samples that are generated by running the chain for a large but fixed number of steps. It does so by using a strategy called “coupling from the past”. Although the sampling mechanism used in their method is typically driven by independent random points, more structured sampling can also be used. Recently, Craiu and Meng [R.V. Craiu, X.-L. Meng, Antithetic coupling for perfect sampling, in: E.I. George (Ed.), Bayesian Methods with Applications to Science, Policy, and Official Statistics (Selected Papers from ISBA 2000), 2000, pp. 99–108; R.V. Craiu, X.-L. Meng, Multi-process parallel antithetic coupling for forward and backward Markov Chain Monte Carlo, Annals of Statistics 33 (2005) 661–697] suggested using different forms of antithetic coupling for that purpose. In this paper, we consider the use of highly uniform point sets to drive the exact sampling in Propp and Wilson’s method, and illustrate the effectiveness of the proposed method with a few numerical examples.     

On characterizing properties of the value sets and the equilibrium point sets of non-cooperative two-person games

In this paper, for certain subfamilies of the family of bounded measurable two-person games in normal form, the value sets are characterized by three properties, called the maximum property, the minimum property and the adjunction property. Furthermore, one of the papers of Vilkas is critically discussed. Finally, for bimatrix games, two systems of characterizing properties for the equilibrium point sets are given.     

Connecting colored point sets

We study the following Ramsey-type problem. Let S=B∪R be a two-colored set of n points in the plane. We show how to construct, in time, a crossing-free spanning tree T(B) for B, and a crossing-free spanning tree T(R) for R, such that both the number of crossings between T(B) and T(R) and the diameters of T(B) and T(R) are kept small. The algorithm is conceptually simple and is implementable without using any non-trivial data structure. This improves over a previous method in Tokunaga [Intersection number of two connected geometric graphs, Inform. Process. Lett. 59 (1996) 331-333] that is less efficient in implementation and does not guarantee a diameter bound. Implicit to our approach is a new proof for the result in the reference above on the minimum number of crossings between T(B) and T(R).     

Bernstein sets with algebraic properties

We construct Bernstein sets in ℝ having some additional algebraic properties. In particular, solving a problem of Kraszewski, Rałowski, Szczepaniak and Żeberski, we construct a Bernstein set which is a < c-covering and improve some other results of Rałowski, Szczepaniak and Żeberski on nonmeasurable sets.     

Zero sets and uniqueness sets with one cluster point for the Dirichlet space

Zero sets and uniqueness sets of the Dirichlet space are not completely characterized yet. There are sufficient conditions for zero sets and necessary conditions for uniqueness sets and there is a gap in between. Our goal is to take some preliminary steps to fill this gap.     

A note on connection properties of fixed point sets of nonexpansive mappings

We consider a discrete-time GALERKIN method for nonlinear evolution equations. We prove convergence properties of this method under various hypotheses. Moreover, we deal with iteration methods reducing the nonlinear GALERKIN equations to linear equations in finite dimensional spaces.     

Halvings on small point sets

A halving is a t-design which has the same parameters as its complementary design. Together these two designs form a large set LS[2](t, k, v). There are several recursion theorems for large sets, such that a single new halving results in several new infinite families of halvings. We present new halvings with the parameters 7-(24, 10, 340), 6-(22, 9, 280), 5-(21, 10, 2184), and 5-(21, 9, 910). Recursive constructions by S. Ajoodani-Namini and G. B. Khosrovshahi [Discrete Math 135 (1994), 29–37; J. Combin. Theory A 76 (1996), 139–144] then yield that an LS[2](t, k, v) exists if and only if the parameter set is admissible for t = 6, k = 7, 8, 9, and for t ≤ 5, k ≤ 15. Thus, Hartman's conjecture is true in these cases. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 233–241, 1999     

Triangulating point sets in space

A setP ofn points inR ^d is called simplicial if it has dimensiond and contains exactlyd + 1 extreme points. We show that whenP containsn interior points, there is always one point, called a splitter, that partitionsP intod + 1 simplices, none of which contain more thandn/(d + 1) points. A splitter can be found inO(d ⁴ +nd ²) time. Using this result, we give anO(nd ⁴ log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. InR ³ we give anO(n logn +k) algorithm for triangulating arbitrary point sets, wherek is the number of simplices produced. We exhibit sets of 2n + 1 points inR ³ for which the number of simplices produced may vary between (n – 1)² + 1 and 2n – 2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.Research supported by the Natural Science and Engineering Research Council grant A3013 and the F.C.A.R. grant EQ1678.     

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.     

Realization of fixed point sets

Letf:XX be a selfmap of a compact connected polyhedron, andA a nonempty closed subset ofX. In this paper, we shall deal with the question whether or not there is a mapg:XX homotopic tof such that the fixed point set Fixg ofg equalsA. We introduce a necessary condition for the existence of such a mapg. It is shown that this condition is easy to check, and hence some sufficient conditions are obtained.Partially supported by the Natural Science Foundation of Liaoning University.     

Bounded-degree polyhedronization of point sets

In 1994 Grünbaum showed that, given a point set S in ${\mathbb{R}}^3$, it is always possible to construct a polyhedron whose vertices are exactly S. Such a polyhedron is called a polyhedronization of S. Agarwal et al. extended this work in 2008 by showing that there always exists a polyhedronization that can be decomposed into a union of tetrahedra (tetrahedralizable). In the same work they introduced the notion of a serpentine polyhedronization for which the dual of its tetrahedralization is a chain. In this work we present a randomized algorithm running in $O(n{\log }^{6}n)$ expected time which constructs a serpentine polyhedronization that has vertices with degree at most 7, answering an open question by Agarwal et al.     

Covering point sets with two disjoint disks or squares

We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks C_R and C_B with disjoint interiors such that the number of red points covered by C_R plus the number of blue points covered by C_B is maximized. We give an algorithm to solve this problem in O(n^8/3log²n) time, where n denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares S_R and S_B instead of unit disks can be solved in O(nlogn) time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using O(n³logn) time.