Add to ORKGAbstract. We give new positive results on the long-standing open problem of geometric covering decomposition for homothetic polygons. In particu-lar, we prove that for any positive integer k, every finite set of points in R3 can be colored with k colors so that every translate of the negative octant containing at least k6 points contains at least one of each color. The best pre-viously known bound was doubly exponential in k. This yields, among other corollaries, the first polynomial bound for the decomposability of multiple coverings by homothetic triangles. We also investigate related decomposition problems involving intervals appearing on a line. We prove that no algorithm can dynamically maintain a decomposition of a multiple covering b...
Given a planar point set and an integer k, we wish to color the points with k colors so that any axi...
To make computations on large data sets more efficient, algorithms will frequently divide informatio...
The topological KKMS Theorem is a powerful extension of Brouwer's Fixed-Point Theorem, which was pro...
International audienceWe give new positive results on the long-standing open problem of geometric co...
$\newcommand{\R}{\mathbb{R}}$In this note we improve our upper bound given in [Keszegh and Pálvölgyi...
We prove that octants are cover-decomposable into multiple coverings, i.e., for any k there is an ...
We prove that for any point set P in the plane, a triangle T, and a positive integer k, there exists...
Abstract. We prove that for any finite point set P in the plane, a triangle T, and a positive intege...
A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one ver...
A coloring of a hypergraph\u27s vertices is polychromatic if every hyperedge contains at least one v...
We prove that every finite set of homothetic copies of a given convex body in the plane can be color...
We study two decomposition problems in combinatorial geometry. The first part deals with the decompo...
AbstractLet m(k) denote the smallest positive integer m such that any m-fold covering of the plane w...
The goal of this paper is to give a new, abstract approach to cover-decomposition and polychromatic ...
We study whether for a given planar family F there is an m such that any finite set of points can be...
Given a planar point set and an integer k, we wish to color the points with k colors so that any axi...
To make computations on large data sets more efficient, algorithms will frequently divide informatio...
The topological KKMS Theorem is a powerful extension of Brouwer's Fixed-Point Theorem, which was pro...
International audienceWe give new positive results on the long-standing open problem of geometric co...
$\newcommand{\R}{\mathbb{R}}$In this note we improve our upper bound given in [Keszegh and Pálvölgyi...
We prove that octants are cover-decomposable into multiple coverings, i.e., for any k there is an ...
We prove that for any point set P in the plane, a triangle T, and a positive integer k, there exists...
Abstract. We prove that for any finite point set P in the plane, a triangle T, and a positive intege...
A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one ver...
A coloring of a hypergraph\u27s vertices is polychromatic if every hyperedge contains at least one v...
We prove that every finite set of homothetic copies of a given convex body in the plane can be color...
We study two decomposition problems in combinatorial geometry. The first part deals with the decompo...
AbstractLet m(k) denote the smallest positive integer m such that any m-fold covering of the plane w...
The goal of this paper is to give a new, abstract approach to cover-decomposition and polychromatic ...
We study whether for a given planar family F there is an m such that any finite set of points can be...
Given a planar point set and an integer k, we wish to color the points with k colors so that any axi...
To make computations on large data sets more efficient, algorithms will frequently divide informatio...
The topological KKMS Theorem is a powerful extension of Brouwer's Fixed-Point Theorem, which was pro...