For a real matrix \(\textbf A \in \mathbb{R}^{d \times n}\) with non-collinear columns, we show that \(n \le O(d^{4} \kappa_\textbf A)\) where \(\kappa_\textbf A\) is the circuit imbalance measure of \(\textbf A\). The circuit imbalance measure \(\kappa\) is a real analogue of \(\Delta\)-modularity for integer matrices, satisfying \(\kappa_\textbf A \le \Delta_\textbf A\) for integer \(\textbf A\). The circuit imbalance measure has numerous applications in the context of linear programming (see Ekkbatani, Natura and Végh (2022) for a survey). Our result generalizes the \(O(d^{4} \Delta_\textbf A)\) bound of Averkov and Schymura (2023) for integer matrices and provides the first polynomial bound holding for all parameter ranges on real matrices.

A long-standing open conjecture of Branko Grünbaum from 1972 states that any arrangement of n pairwise intersecting pseudocircles in the plane can have at most 2n-2 digons. Agarwal et al. proved this conjecture for arrangements in which there is a common point surrounded by all pseudocircles. Recently, Felsner, Roch and Scheucher showed that Grünbaum’s conjecture is true for arrangements of pseudocircles in which there are three pseudocircles every pair of which creates a digon. In this paper we prove this over 50-year-old conjecture of Grünbaum for any arrangement of pairwise intersecting circles in the plane.

We show that for any integer $n \geq 1$ and real $\varepsilon > 0$, the union of $n$ arithmetic progressions with pairwise distinct differences, each of length $n$, contains at least $c(\varepsilon)n^{2-\varepsilon}$ elements, where $c(\varepsilon)$ is a positive constant depending only on $\varepsilon$. This estimate is sharp in the sense that the assertion becomes invalid for $\varepsilon=0$. We also obtain estimates for the “asymmetric case" where the number of progressions is distinct from their lengths. (A corrected PDF is attached.)

We show that there is an absolute constant $c \leq 156$ such that in every finite family ${\cal F}$ of pseudodiscs in the plane one can find a member $D \in {\cal F}$ such that among all of the pseudodiscs in ${\cal F}$ intersecting $D$ there are at most $c$ pairwise disjoint sets.

Given a set P of points in the plane we are interested in points that are 'deep' in the set in the sense that they have two opposite quadrants both containing many points of P. We deal with the extremal version of this problem. A pair (a, b) of numbers is admissible if every point set P contains a point p ∈ P that determines a pair (Q,Qop) of opposite quadrants, such that Q contains at least an a-fraction and Qop contains at least a b-fraction of the points of P. We provide a complete description of the set F of all admissible pairs (a, b). This amounts to identifying three line segments and a point on the boundary of F.

Let d be a fixed integer, and let W be any d-dimensional linear subspace of $\mathbb{R}^n$. There then exists a subset I of the n coordinates $\{1,2,\dots,n\}$ of $\mathbb{R}^n$ of cardinality at least $(\frac{1}{2}-o(1))n$ such that for every vector $w=(w_1,\dots,w_n)\in W$ we have $\sum_{i\in I}|w_i|\leq\sum_{i\notin I}|w_i|$. Equivalently, let P be any multiset of n arbitrary vectors in $\mathbb{R}^d$. Then there exists a subset S of P of size at least $(\frac{1}{2}-o(1))n$ such that for every vector $u\in\mathbb{R}^d$ we have $\sum_{x\in S}|\langle x,u\rangle|\leq\sum_{x\in P\setminus S}|\langle x,u\rangle|$. A continuous analogue of the former result is also considered.

Given a set P of n points in the plane and a collection of k halving lines of P l1, ..., lk, indexed according to the increasing order of their slopes, we denote by d(lj,lj+1) the number of points in P that lie above lj+1 and below lj. We prove an upper bound of 3nk1/3 for the sum sumj=1k-1d(lj,lj+1). We show how this problem is related to the halving lines problem and provide several consequences about measure concentration in R2.

Let P be a set of n points in the plane and let C be a family of simple closed curves in the plane each of which avoids the points of P. For every curve C ∈ C we denote by disc(C) the region in the plane bounded by C. Fix an integer s > 0 and assume that every two curves in C intersect at most s times and that for every two curves C,C' ∈ C the intersection disc(C) ∩ disc(C') is a connected set. We consider the family F = {P ∩ disc(C) | C ∈ C}. When s is even, we provide sharp bounds, in terms of n, s, and k, for the number of sets in F of cardinality k, assuming that ∩C ∈Cdisc(C) is nonempty. In particular, we provide sharp bounds for the number of halving pseudo-parabolas for a set of n points in the plane. Finally, we consider the VC-dimension of F and show that F has VC-dimension at most s+1.

We prove a conjecture of Erdős, Purdy, and Straus on the number of distinct areas of triangles determined by a set of n points in the plane. We show that if P is a set of n points in the plane, not all on one line, then P determines at least $\lfloor\frac{n-1}{2}\rfloor$ triangles with pairwise distinct areas. Moreover, one can find such $\lfloor\frac{n-1}{2}\rfloor$ triangles all sharing a common edge.

A finite planar point set P is called a magic configuration if there is an assignment of positive weights to the points of P such that, for everyline l determined by P, the sum of the weights of all points of P on l equals 1. We prove a conjecture of Murty from 1971 and show that a magic configuration consists either of points in general position, or all points are collinear, with the possible exception of one point, or they form a special configuration of 7 points.

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.

Let P be a set of n points in ℝ3, not all in a common plane. We solve a problem of Scott (1970) by showing that the connecting lines of P assume at least 2n-7 different directions if n is even and at least 2n-5 if n is odd. The bound for odd n is sharp.

Let P be a set of n points in general position in the plane. Let Xk(P) denote the number of empty convex κ-gons determined by P. We derive, using elementary proof techniques, several equalities and inequalities involving the quantities Xk(P) and several related quantities. Most of these equalities and inequalities are new, except for a couple that have been proved earlier using a considerablymore complex machinery from matroid and polytope theory,algebraic topology and commutative algebra. Some of these relationships are also extended to higher dimensions. We present several implications of these relationships, and discuss their connection with several long-standing open problems, the most notorious of which is the existence of an empty convex hexagon in any point set with sufficiently many points.

A geometric graph is a simple graph G=(V,E) with an embedding of the set V in the plane such that the points that represent V are in general position. A geometric graph is said to be k-locally Delaunay (or a Dk-graph) if for each edge (u,v) ∈ E there is a (Euclidean) disc d that contains u and v but no other vertex of G that is within k hops from u or v.The study of these graphs was recently motivated by topology control for wireless networks [6,7]. We obtain the following results: (i) We prove that if G is a D1-graph on n vertices, then it has O(n3/2) edges. (ii) We show that for any n there exist D1-graphs with n vertices and Ω(n4/3) edges. (iii) We prove that if G is a D2-graph on n vertices, then it has O(n) edges. This bound is worst-case asymptotically tight. As an application of the first result, we show that: (iv) The maximum size of a family of pairwise non-overlapping lenses in an arrangement of $n$ unit circles in the plane is O(n3/2).The first two results improve the best previously known upper and lower bounds of $O(n^ 5/3 )$ and $\Omega(n)$ respectively (see \cite KL03 ). The third result improves the best previously known upper bound of O(n log n ) ([6]). Finally, our last result improves the best previously known upper bound (for the more general case of not necessarily unit circles) of O(n3/2 κ(n)) (see [1] ), where κ(n) = (log n ) O(α2(n)) and where α(n) is the extremely slowly growing inverse Ackermann's function.

A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if the closed Jordan region that it bounds does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. We use this bound to show that any collection of n x -monotone pseudo-circles can be cut into O ( n 8/5 ) arcs so that any two intersect at most once; this improves a previous bound of O ( n 5/3 ) due to Tamaki and Tokuyama. If, in addition, the given collection admits an algebraic representation by three real parameters that satisfies some simple conditions, then the number of cuts can be further reduced to O ( n 3/2 (log n ) O (α( s ( n )) ), where α( n ) is the inverse Ackermann function, and s is a constant that depends on the the representation of the pseudo-circles. For arbitrary collections of pseudo-circles, any two of which intersect exactly twice, the number of necessary cuts reduces still further to O ( n 4/3 ). As applications, we obtain improved bounds for the number of incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, of pairwise intersecting pseudo-circles, of arbitrary x -monotone pseudo-circles, of parabolas, and of homothetic copies of any fixed simply shaped convex curve. We also obtain a variant of the Gallai--Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound on the number of distinct distances under any well-behaved norm.

Let P be a set of n points in R3, not all of which are in a plane and no three on a line. We partially answer a question of Scott (1970) by showing that the connecting lines of P assume at least 2n-3 different directions if n is even and at least 2n-2 if n is odd. These bounds are sharp. The proof is based on a far-reaching generalization of Ungar's theorem concerning the analogous problem in the plane.

Let G be a topological graph on n vertices in the plane, i.e., a graph drawn in the plane with its vertices represented as points and its edges represented as Jordan arcs connecting pairs of points. It is shown that if no two edges of any cycle of length 4 in G cross an odd number of times, then |E(G)|=O(n8/5).

(MATH) A collection of simple closed Jordan curves in the plane is called a family of pseudo-circles if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an empty lens if it does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of n pseudo-circles with the property that any two curves intersect precisely twice. Enhancing this bound in several ways, and combining it with the technique of Tamaki and Tokuyama [16], we show that any collection of n pseudo-circles can be cut into $\bx$ arcs so that any two intersect at most once, provided that the given pseudo-circles are x-monotone and admit an algebraic representation by three real parameters; here $\alpha(n)$ is the inverse Ackermann function, and s is a constant that depends on the algebraic degree of the representation of the pseudo-circles (s=2 for circles and parabolas). For arbitrary collections of pseudo-circles, any two of which intersect twice, the number of necessary cuts reduces to O(n 4/3). As applications, we obtain improved bounds for the number of point-curve incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, pairwise intersecting pseudo-circles, parabolas, and families of homothetic copies of a fixed convex curve. We also obtain a variant of the Gallai-Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound for the number of distinct distances among n points in the plane under any simply-defined norm or convex distance function.