On iterative processes generating dense point sets

Summary The central problem of this paper is the question of denseness of those planar point sets <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[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>\mathcal{P}$, not a subset of a line, which have the property that for every three noncollinear points in $\mathcal{P}$, a specific triangle center (incenter (IC), circumcenter (CC), orthocenter (OC) resp.) is also in the set $\mathcal{P}$. The IC and CC versions were settled before. First we generalize and solve the CC problem in higher dimensions. Then we solve the OC problem in the plane essentially proving that $\mathcal{P}$ is either a dense point set of the plane or it is a subset of a rectangular hyperbola. In the latter case it is either a dense subset or it is a special discrete subset of a rectangular hyperbola.     

Sumsets of dense sets and sparse sets

R. Jin showed that whenever A and B are sets of integers having positive upper Banach density, the sumset A+B:= «a+b: a ∈ A, b ∈ B» is piecewise syndetic. This result was strengthened by Bergelson, Furstenberg, and Weiss to conclude that A+B must be piecewise Bohr. We generalize the latter result to cases where A has Banach density 0, giving a new proof of the previous results in the process.     

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.     

Thin-type dense sets and related properties

We build on Gruenhage, Natkaniec, and Piotrowski?s study of thin, very thin, and slim dense sets in products, and the related notions of (NC) and (GC) which they introduced. We find examples of separable spaces X such that X² has a thin or slim dense set but no countable one. We characterize ordered spaces that satisfy (GC) and (NC), and we give an example of a separable space which satisfies (GC) but not witnessed by a collection of finite sets. We show that the question of when the topological sum of two countable strongly irresolvable spaces satisfies (NC) is related to the Rudin-Keisler order on βω. We also introduce and study the concepts of <κ-thin and superslim dense sets.     

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.     

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.     

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

A base-matrix lemma for sets of rationals modulo nowhere dense sets

We study some properties of the quotient forcing notions ${Q_{tr(I)} = \wp(2^{< \omega})/tr(I)}$ and P _I ?= B(2 ^ω )/I in two special cases: when I is the σ-ideal of meager sets or the σ-ideal of null sets on 2 ^ω . We show that the remainder forcing R _I =?Q _tr(I)/P _I is σ-closed in these cases. We also study the cardinal invariant of the continuum ${\mathfrak{h}_{\mathbb{Q}}}$ , the distributivity number of the quotient ${Dense(\mathbb{Q})/nwd}$ , in order to show that ${\wp(\mathbb{Q})/nwd}$ collapses ${\mathfrak{c}}$ to ${\mathfrak{h}_{\mathbb{Q}}}$ , thus answering a question addressed in Balcar et?al. (Fundamenta Mathematicae 183:59–80, 2004).     

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     

Convex independent sets and 7-holes in restricted planar point sets

For a finite setA of points in the plane, letq(A) denote the ratio of the maximum distance of any pair of points ofA to the minimum distance of any pair of points ofA. Fork>0 letc (k) denote the largest integerc such that any setA ofk points in general position in the plane, satisfying for fixed , contains at leastc convex independent points. We determine the exact asymptotic behavior ofc (k), proving that there are two positive constants=(), such thatk ^1/3c (k)k ^1/3. To establish the upper bound ofc (k) we construct a set, which also solves (affirmatively) the problem of Alonet al. [1] about the existence of a setA ofk points in general position without a 7-hole (i.e., vertices of a convex 7-gon containing no other points fromA), satisfying . The construction uses Horton sets, which generalize sets without 7-holes constructed by Horton and which have some interesting properties.     

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.