EAEyal Ackerman

Eyal Ackerman

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Eyal Ackerman has a total of 12 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    On Partitions of Two-Dimensional Discrete Boxes

    by Eyal Ackerman, Rom Pinchasi

    Let $A$ and $B$ be finite sets and consider a partition of the \emph{discrete box} $A \times B$ into \emph{sub-boxes} of the form $A' \times B'$ where $A' \subset A$ and $B' \subset B$. We say that such a partition has the $(k,\ell)$-piercing property for positive integers $k$ and $\ell$ if every \emph{line} of the form $\{a\} \times B$ intersects at least $k$ sub-boxes and every line of the form $A \times \{b\}$ intersects at least $\ell$ sub-boxes. We show that a partition of $A \times B$ that has the $(k, \ell)$-piercing property must consist of at least $(k-1)+(\ell-1)+\left\lceil 2\sqrt{(k-1)(\ell-1)} \right\rceil$ sub-boxes. This bound is nearly sharp (up to one additive unit) for every $k$ and $\ell$. As a corollary we get that the same bound holds for the minimum number of vertices of a graph whose edges can be colored red and blue such that every vertex is part of red $k$-clique and a blue $\ell$-clique.

  • Open Access

    An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons

    by Eyal Ackerman, Balázs Keszegh, Günter Rote

    What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even: If both m and n are even, then every pair of sides may cross and so the answer is mn. If exactly one polygon, say the n-gon, has an odd number of sides, it can intersect each side of the m-gon polygon at most $$n-1$$ n - 1 times; hence there are at most $$mn-m$$ m n - m intersections. It is not hard to construct examples that meet these bounds. If both m and n are odd, the best known construction has $$mn-(m+n)+3$$ m n - ( m + n ) + 3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only $$mn-(m + \lceil {n}/{6} \rceil )$$ m n - ( m + ⌈ n / 6 ⌉ ) , for $$m \ge n$$ m ≥ n . We prove a new upper bound of $$mn-(m+n)+C$$ m n - ( m + n ) + C for some constant C, which is optimal apart from the value of C.

  • Coloring Delaunay-edges and their generalizations

    by Eyal Ackerman, Balázs Keszegh, Dömötör Pálvölgyi


  • Open Access

    Coloring Delaunay-Edges and their Generalizations

    by Eyal Ackerman, Balázs Keszegh, Dömötör Pálvölgyi

    We consider geometric hypergraphs whose vertex set is a finite set of points (e.g., in the plane), and whose hyperedges are the intersections of this set with a family of geometric regions (e.g., axis-parallel rectangles). A typical coloring problem for such geometric hypergraphs asks, given an integer $k$, for the existence of an integer $m=m(k)$, such that every set of points can be $k$-colored such that every hyperedge of size at least $m$ contains points of different (or all $k$) colors. We generalize this notion by introducing coloring of \emph{$t$-subsets} of points such that every hyperedge that contains enough points contains $t$-subsets of different (or all) colors. In particular, we consider all $t$-subsets and $t$-subsets that are themselves hyperedges. The latter, with $t=2$, is equivalent to coloring the edges of the so-called \emph{Delaunay-graph}. In this paper we study colorings of Delaunay-edges with respect to halfplanes, pseudo-disks, axis-parallel and bottomless rectangles, and also discuss colorings of $t$-subsets of geometric and abstract hypergraphs, and connections between the standard coloring of vertices and coloring of $t$-subsets of vertices.

  • Open Access

    An almost optimal bound on the number of intersections of two simple polygons

    by Eyal Ackerman, Balázs Keszegh, Günter Rote

    What is the maximum number of intersections of the boundaries of a simple $m$-gon and a simple $n$-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of $m$ and $n$ is even: If both $m$ and $n$ are even, then every pair of sides may cross and so the answer is $mn$. If exactly one polygon, say the $n$-gon, has an odd number of sides, it can intersect each side of the $m$-gon at most $n-1$ times; hence there are at most $mn-m$ intersections. It is not hard to construct examples that meet these bounds. If both $m$ and $n$ are odd, the best known construction has $mn-(m+n)+3$ intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only $mn-(m + \lceil \frac{n}{6} \rceil)$, for $m \ge n$. We prove a new upper bound of $mn-(m+n)+C$ for some constant $C$, which is optimal apart from the value of $C$.

  • Open Access

    On topological graphs with at most four crossings per edge

    by Eyal Ackerman

    We show that if a graph $G$ with $n \geq 3$ vertices can be drawn in the plane such that each of its edges is involved in at most four crossings, then $G$ has at most $6n-12$ edges. This settles a conjecture of Pach, Radoi\v{c}i\'{c}, Tardos, and T\'oth, and yields a better bound for the famous Crossing Lemma: The crossing number, $\mbox{cr}(G)$, of a (not too sparse) graph $G$ with $n$ vertices and $m$ edges is at least $c\frac{m^3}{n^2}$, where $c > 1/29$. This bound is known to be tight, apart from the constant $c$ for which the previous best lower bound was $1/31.1$. As another corollary we obtain some progress on the Albertson conjecture: Albertson conjectured that if the chromatic number of a graph $G$ is $r$, then $\mbox{cr}(G) \geq \mbox{cr}(K_r)$. This was verified by Albertson, Cranston, and Fox for $r \leq 12$, and for $r \leq 16$ by Bar\'at and T\'oth. Our results imply that Albertson conjecture holds for $r \leq 18$.

  • Open Access

    Coloring points with respect to squares

    by Eyal Ackerman, Balázs Keszegh, Máté Vizer

    We consider the problem of $2$-coloring geometric hypergraphs. Specifically, we show that there is a constant $m$ such that any finite set of points in the plane $\mathcal{S} \subset {\mathbb R}^2$ can be $2$-colored such that every axis-parallel square that contains at least $m$ points from $\mathcal{S}$ contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a $2$-coloring. By affine transformations this result immediately applies also when considering $2$-coloring points with respect to homothets of a fixed parallelogram.

  • On the Size of Planarly Connected Crossing Graphs

    by Eyal Ackerman, Balázs Keszegh, Mate Vizer


  • Open Access

    On the size of planarly connected crossing graphs

    by Eyal Ackerman, Balázs Keszegh, Mate Vizer

    We prove that if an $n$-vertex graph $G$ can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then $G$ has $O(n)$ edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal $1$-planar and fan-planar graphs.