Finite unions of convex sets are a central object of study in discrete and computational geometry. In this paper we initiate a systematic study of complements of such unions - i.e., sets of the form S = ℝ^d ⧵ (∪_{i=1}^n K_i), where K_i are convex sets. In the first part of the paper we study isolated points in S, whose number is related to the Betti numbers of ∪_{i=1}^n K_i and to its non-convexity properties. We obtain upper bounds on the number of such points, which are sharp for n = 3 and significantly improve previous bounds of Lawrence and Morris (2009) for all n ≪ 2^d/d. In the second part of the paper we study coverings of S by well-behaved sets. We show that S can be covered by at most g(d,n) flats of different dimensions, in such a way that each x ∈ S is covered by a flat whose dimension equals the "local dimension" of S in the neighborhood of x. Furthermore, we determine the structure of a minimum cover that satisfies this property. Then, we study quantitative aspects of this minimum cover and obtain sharp upper bounds on its size in various settings.

A family ℱ of sets satisfies the (p,q)-property if among every p members of ℱ, some q can be pierced by a single point. The celebrated (p,q)-theorem of Alon and Kleitman asserts that for any p ≥ q ≥ d+1, any family ℱ of compact convex sets in ℝ^d that satisfies the (p,q)-property can be pierced by a finite number c(p,q,d) of points. A similar theorem with respect to piercing by (d-1)-dimensional flats, called (d-1)-transversals, was obtained by Alon and Kalai. In this paper we prove the following result, which can be viewed as an (ℵ₀,k+2)-theorem with respect to k-transversals: Let ℱ be an infinite family of sets in ℝ^d such that each A ∈ ℱ contains a ball of radius r and is contained in a ball of radius R, and let 0 ≤ k < d. If among every ℵ₀ elements of ℱ, some k+2 can be pierced by a k-dimensional flat, then ℱ can be pierced by a finite number of k-dimensional flats. This is the first (p,q)-theorem in which the assumption is weakened to an (∞,⋅) assumption. Our proofs combine geometric and topological tools.

For a family ℱ of non-empty sets in ℝ^d, the Krasnoselskii number of ℱ is the smallest m such that for any S ∈ ℱ, if every m or fewer points of S are visible from a common point in S, then any finite subset of S is visible from a single point. More than 35 years ago, Peterson asked whether there exists a Krasnoselskii number for general sets in ℝ^d. The best known positive result is Krasnoselskii number 3 for closed sets in the plane, and the best known negative result is that if a Krasnoselskii number for general sets in ℝ^d exists, it cannot be smaller than (d+1)². In this paper we answer Peterson’s question in the negative by showing that there is no Krasnoselskii number for the family of all sets in ℝ². The proof is non-constructive, and uses transfinite induction and the well-ordering theorem. In addition, we consider Krasnoselskii numbers with respect to visibility through polygonal paths of length ≤ n, for which an analogue of Krasnoselskii’s theorem for compact simply connected sets was proved by Magazanik and Perles. We show, by an explicit construction, that for any n ≥ 2, there is no Krasnoselskii number for the family of compact sets in ℝ² with respect to visibility through paths of length ≤ n. (Here the counterexamples are finite unions of line segments.)

Let A be a set of nonnegative integers. We say that A is skippable if there are arbitrary large finite sets of points in the plane, not contained in a line, that determine no k‐edge for any $k \in A$. In this paper we show, by construction, that there are arbitrary large skippable sets. We also characterize precisely the skippable sets with at most two elements.

A definite automaton is, roughly speaking, an automaton (sequential circuit) with the property that for some fixed integer k its action depends only on the last k inputs. The notion of a definite event introduced by Kleene, as well as the related concepts of definite automata and tables, are studied here in detail. Basic results relating to the minimum number of states required for synthesizing an automaton of a given degree of definiteness are proved. We give a characterization of all k-definite events definable by k+1 state automata. Various decision problems pertaining to definite automata are effectively solved. We also solve effectively the problem of synthesizing a minimal automaton defining a given definite event. The solutions of decision and synthesis problems given here are practical in the sense that if the problem is presented by n units of information, then the algorithm in question requires about n3 steps of a very elementary nature (rather than requiring about 2n steps as some algorithms for automata do, which puts them beyond the capacity of the largest computers even for relatively small values of n). A notion of equivalence of definite events is introduced and the uniqueness of the minimal automaton defining an event in an equivalence class is proved.