Abstract. We consider the minimum number of lines [Formula: see text] and [Formula: see text] needed to intersect or pierce, respectively, all the cells of the [Formula: see text] chessboard. Determining these values can also be interpreted as a strengthening of the classical plank problem for integer points. Using the symmetric plank theorem of K. Ball, we prove that [Formula: see text] for each [Formula: see text]. Studying the piercing problem, we show that [Formula: see text] for [Formula: see text], where the upper bound is conjectured to be sharp. The lower bound is proven by using the linear programming method, whose limitations are also demonstrated.

For a finite set A ⊂ ℝ², a map φ: A → ℝ² is orientation preserving if for every non-collinear triple u,v,w ∈ A the orientation of the triangle u,v,w is the same as that of the triangle φ(u),φ(v),φ(w). We prove that for every n ∈ ℕ and for every ε > 0 there is N = N(n,ε) ∈ ℕ such that the following holds. Assume that φ:G(N) → ℝ² is an orientation preserving map where G(N) is the grid {(i,j) ∈ ℤ²: -N ≤ i,j ≤ N}. Then there is an affine transformation ψ :ℝ² → ℝ² and a ∈ ℤ² such that a+G(n) ⊂ G(N) and ‖ψ∘φ (z)-z‖ < ε for every z ∈ a+G(n). This result was previously proved in a completely different way by Nešetřil and Valtr, without obtaining any bound on N. Our proof gives N(n,ε) = O(n⁴ε^{-2}).

Motivated by Barman [6], we initiate a systematic study of the ‘no-dimensional’ analogues of some basic theorems in combinatorial and convex geometry, including the colorful Carathéodory's theorem, Tverberg's theorem, Helly's theorem as well as their fractional and colorful extensions.

By a curve in Rd we mean a continuous map γ: I → Rd, where I ⊂ R is a closed interval. We call a curve γ in Rd (≤ k)-crossing if it intersects every hyperplane at most k times (counted with multiplicity). The (≤ d)-crossing curves in Rd are often called convex curves and they form an important class; a primary example is the moment curve {(t, t2, …, td): t ∈ [0, 1]}. They are also closely related to Chebyshev systems, which is a notion of considerable importance, e.g., in approximation theory. Our main result is that for every d there is M = M(d) such that every (≤ d + 1)-crossing curve in Rd can be subdivided into at most M(≤ d)-crossing curve segments. As a consequence, based on the work of Eliáš, Roldán, Safernová, and the second author, we obtain an essentially tight lower bound for a geometric Ramsey-type problem in Rd concerning order-type homogeneous sequences of points, investigated in several previous papers.

In his paper "On sets of distances of n points", Paul Erdos conjectured that every convex curve contains a point P such that every circle centered at P intersects the curve in at most 2 points. This conjecture is false: If T is an equilateral triangle with boundary T, for any point P on T there is a circle centered at P that intersects T at 4 points. But perhaps the number 2 in Erdos's conjecture can be replaced by some other number.

Giving a (partial) solution to a problem of Fekete [Geometry and the Traveling Salesman Problem, Ph.D. thesis, University of Waterloo, Waterloo, ON, Canada, 1992] and Fekete and Woeginger [Comput. Geom., 8 (1997), pp. 195–218], we show that given a finite set X of points in the plane, it is possible to find a polygonal path with $|X|-1$ segments and with vertex set X so that every angle on the polygonal path is at least $\pi/9$. According to a conjecture of Fekete and Woeginger, $\pi/9$ can be replaced by $\pi/6$. Previously, the result has not been known with any positive constant. We show further that the same result holds, with an angle smaller than $\pi/9$, in higher dimensions.

The colorful Carathéodory theorem asserts that if $X_1,X_2,\ldots,X_{d+1}$ are sets in ${\bf R}^d$, each containing the origin 0 in its convex hull, then there exists a set $S \subseteq X_1 \cup \cdots \cup X_{d+1}$ with $|S \cap X_i| = 1$ for all $i=1,2,\ldots,d+1$ and $0 \in conv(S)$ (we call $conv(S)$ a colorful covering simplex). Deza et al. [Discrete Comput. Geom., 35 (2006), pp. 597–615] proved that if the $X_i$ are in general position with respect to 0 (consequently, each $X_i$ has at least $d+1$ points), then there are at least $2d$ colorful covering simplices, and they constructed an example with no more than $d^2+1$ such simplices. Under the same assumption, we show that there are at least $\frac{1}{5}d(d+1)$ colorful covering simplices, thus determining the order of magnitude. A similar result was proved independently by Stephen and Thomas [http://www.arxiv.org/abs/math.CO/0512400 (2005)]. We also obtain a lower bound of $3d$ for $d \geq 3$, which is better for small d and, in particular, together with a parity argument it settles the case $d=3$, where the minimum possible number of colorful covering simplices is 10.

We consider Nash equilibria in 2-player random games and analyze a simple Las Vegas algorithm for finding an equilibrium. The algorithm is combinatorial and always finds a Nash equilibrium; on m /spl times/ n payoff matrices, it runs in time O(m/sup 2/n log log n + n/sup 2/m log log m) with high probability. Our main tool is a polytope formulation of equilibria.

Article Free Access Share on On the convex hull of the integer points in a disc Authors: Antal Balog Institute for Advanced Study, Princeton, NJ Institute for Advanced Study, Princeton, NJView Profile , Imre Bárány Yale University, New Haven, CT and NYU, New York, NY Yale University, New Haven, CT and NYU, New York, NYView Profile Authors Info & Claims SCG '91: Proceedings of the seventh annual symposium on Computational geometryJune 1991 Pages 162–165https://doi.org/10.1145/109648.109666Published:01 June 1991Publication History 30citation414DownloadsMetricsTotal Citations30Total Downloads414Last 12 Months48Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let S ⊂ R3 be an n-set in general position. A plane containing three of the points is called a halving plane if it dissects S into two parts of equal cardinality. It is proved that the number of halving planes is at most Ο(n2.998).

Article Computing the volume is difficult Share on Authors: Z Furedi View Profile , I Barany View Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 442–447https://doi.org/10.1145/12130.12176Online:01 November 1986Publication History 15citation351DownloadsMetricsTotal Citations15Total Downloads351Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access