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
Research Subjects
Eyal Ackerman has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Balázs Keszegh
HUN-REN Alfréd Rényi Institute of Mathematics ELTE Eötvös Loránd University Budapest Hungary
7 shared publications - Rom Pinchasi
Mathematics Department, Technion, Haifa, Israel
7 shared publications - Máté Vizer
ALFRÉD RÉNYI INSTITUTE OF MATHEMATICS BUDAPEST HUNGARY
3 shared publications Rom Pinchasi
3 shared publicationsDömötör Pálvölgyi
2 shared publications- Günter Rote
Institut für Informatik, Freie Universität Berlin
2 shared publications
Latest Publications
- Open Access
On Partitions of Two-Dimensional Discrete Boxes
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 AccessOn Partitions of Two-Dimensional Discrete Boxes
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
- 12 October 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 68 (4) , 1049-1077
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons
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$$ 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 {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.- 12 October 2022
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 68 (4) , 1049-1077
Open AccessAn Almost Optimal Bound on the Number of Intersections of Two Simple Polygons
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$$ 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 {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. - 1 June 2021
- Published by Elsevier in Computational Geometry
- Vol. 96
Coloring Delaunay-edges and their generalizations
- 1 June 2021
- Published by Elsevier in Computational Geometry
- Vol. 96
Coloring Delaunay-edges and their generalizations
- Open Access
Coloring Delaunay-Edges and their Generalizations
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 AccessColoring Delaunay-Edges and their Generalizations
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
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 AccessAn almost optimal bound on the number of intersections of two simple polygons
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
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 AccessOn topological graphs with at most four crossings per edge
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
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.Open AccessColoring points with respect to squares
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. - 8 December 2016
- Published by Springer Nature
- p. 311-320
On the Size of Planarly Connected Crossing Graphs
- 8 December 2016
- Published by Springer Nature
- p. 311-320
On the Size of Planarly Connected Crossing Graphs
- Open Access
On the size of planarly connected crossing graphs
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.Open AccessOn the size of planarly connected crossing graphs
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.