Assume $X_n$ is a random sample of $n$ uniform, independent points from a triangle $T$. The longest convex chain, $Y$, of $X_n$ is defined naturally. The length $|Y|$ of $Y$ is a random variable,...
Jarnik's convex lattice $n$-gon for non-symmetric norms (2009)
Barany, Imre, Enriquez, Nathanael
What is the minimum perimeter of a convex lattice $n$-gon? This question was answered by Jarnik in 1926. We solve the same question in the case when perimeter is measured by a (not necessarily...
Jarnik's convex lattice $n$-gon for non-symmetric norms (2009)
Barany, Imre, Enriquez, Nathanael
What is the minimum perimeter of a convex lattice $n$-gon? This question was answered by Jarnik in 1926. We solve the same question in the case when perimeter is measured by a (not necessarily...
TEST SETS IN INTEGER PROGRAMMING AND THE COMPLEX OF MAXIMAL LATTICE FREE CONVEX BODIES (2008)
Abstract. For a certain class of integer programming problems, test sets can be used to decide the optimality of a feasible solution. The vectors in the test set correspond to lattice point free...
Integer Points in Rotating Convex Bodies (2007)
Let K be a planar convex body symmetric about the origin. We define P (K) as the probability of K " Z 2 6= f0g, where 2 SO(2) is a random rotation around the origin and Z 2 denotes the integer...
Simultaneous Partitions of Measures By K-Fans (2007)
A k-fan is a point in the plane and k semilines emanating from it. Motivated by a neat question of A. Kaneko and M. Kano, we study equipartitions by k-fans of two or more probability measures in the...
The Randomized Integer Convex Hull (2007)
Imre Barany, Jiri Matousek, Let K R
Let K R be a suciently round convex body (the ratio of the circumscribed ball to the inscribed ball is bounded by a constant) of a suciently large volume. We investigate the randomized integer convex...
Strictly convex drawings of planar graphs (2005)
Every three-connected planar graph with n vertices has a drawing on an O(n^2) x O(n^2) grid in which all faces are strictly convex polygons. These drawings are obtained by perturbing (not strictly)...
A Note on the Size of the Largest Ball Inside a Convex Polytope (2005)
Let $m>1$ be an integer, $B_m$ the set of all unit vectors of $\Bbb R^m$ pointing in the direction of a nonzero integer vector of the cube $[-1, 1]^m$. Denote by $s_m$ the radius of the largest ball...
Planar Point Sets With a Small Number of Empty Convex Polygons (2004)
Imre Barany, Imre B, Pavel Valtr
A subset A of a nite set P of points in the plane is called an empty polygon, if each point of A is a vertex of the convex hull of A and the convex hull of A contains no other points of P . We...
Total curvature and spiralling shortest paths (2003)
Barany, Imre, Kuperberg, Krystyna, Zamfirescu, Tudor
This paper gives a partial confirmation of a conjecture of P. Agarwal, S. Har-Peled, M. Sharir, and K. Varadarajan that the total curvature of a shortest path on the boundary of a convex polyhedron...
The Minimum Area of Convex Lattice n-Gons (2002)
Imre Barany, Norihide Tokushige
Let A(n) be the minimum area of convex lattice n-gons. We prove that lim A(n)/n³ exists. Our computations suggest that the value of the limit is very close to 0.0185067... .
Random Points, Convex Bodies, Lattices (2002)
Assume K is a convex body in R^d, and X is a (large) finite subset of K. How many convex polytopes are there whose vertices come from X? What is the typical shape of such a polytope? How well the...
A Central Limit Theorem for Convex Chains in the Square (1998)
Imre Barany, G Rote, Günter Rote, William Steiger, William Steiger, Cun-hui Zhang, ...
Points P 1 , ...,Pn in the unit square define a convex n-chain if they are below y = x and, together with P 0 = (0, 0) and Pn+1 = (1, 1), they are in convex position. Under uniform probability, we...
The Complex of Maximal Lattice Free Simplices
Imre Barany, Roger Howe, Herbert E. Scarf
The simplicial complex K(A) is defined to be the collection of simplices, and their proper subsimplices, representing maximal lattice free bodies of the form {x : Ax
On Integer Points in Polyhedra: A Lower Bound
Imre Barany, Roger Howe, Laszlo Lovasz
Given a polyhedron we write P(I) for the convex hull of the integral points in P. It is know that P(I) can have at most O(fi(n-1)) vertices if P is a rational polyhedron with size fi. Here we give an...
The Topological Structure of Maximal Lattice Free Convex Bodies: The General Case
Imre Barany, Herbert E. Scarf, David F. Shallcross
Given a generic m x n matrix A, the simplicial complex {bold K}(A) is defined to be the collection of simplices representing maximal lattice point free convex bodies of the form {x : Ax
Matrices with Identical Sets of Neighbors
Given a generic m by n matrix A, a lattice point h in {bold Z} is a neighbor of the origin if the body {x : Ax
Classification of Two-Person Ordinal Bimatrix Games
Imre Barany, J. Lee, Martin Shubik
The set of possible outcomes of a strongly ordinal bimatrix game is studied by imbedding each pair of possible payoffs as a point on the standard two-dimensional integral lattice. In particular, we...
On the Convex Hull of the Integer Points
Let P_{r} denote the convex hull of the integer points in the disc of radius r. We prove that the number of vertices of P_{r} is essentially r^{2/3} as r approaches infinity.
A Colored Version of Tverberg's Theorem
The main result of this paper is that given n red, n white, and n green points in the plane, it is possible to form n vertex-disjoint triangles Delta_{1},...,Delta_{n} in such a way that the...