# Computational Electromagnetics with the RBF-FD Method
††thanks: The authors would like to acknowledge the financial support of the
ARRS in the framework of the research core funding No. P2-0095, the Young
Researcher program PR-12347 and research project J2-3048.

Andrej Kolar-Požun  Parallel and Distributed Systems Laboratory,
’Jožef Stefan’ Institute,
Ljubljana, Slovenia
and
Faculty of Mathematics and Physics,
University of Ljubljana,
Ljubljana, Slovenia
<EMAIL_ADDRESS>Gregor Kosec  Parallel and Distributed Systems
Laboratory,
’Jožef Stefan’ Institute,
Ljubljana, Slovenia
<EMAIL_ADDRESS>
###### Abstract

One of the most popular methods employed in computational electromagnetics is
the Finite Difference Time Domain (FDTD) method. We generalise it to a
meshless setting using the Radial Basis Function generated Finite Difference
(RBF-FD) method and investigate its properties on a simple test problem.

###### Index Terms:

meshless, rbf-fd, electromagnetics, fdtd, yee, maxwell

##  I Introduction

Accurate simulations of electromagnetic field propagation are of great
importance in further development of wireless networks. One of the most
popular simulation procedures is solving the Maxwell’s equations using the
Finite Difference Time Domain (FDTD) method, which was proposed by Kane S. Yee
over 50 years ago [1]. While Yee’s algorithm provides accurate and reliable
results, the fact that it is based on a grid-like discretisation is its
weakness as it becomes impractical to describe fine geometric features, which
is necessary for many real-world applications such as wave propagation in
irregular domains or electromagnetic scattering on antennas of unusual shapes.

Several alternative procedures have been developed that remedy this [2, 3, 4,
5, 6]. Among these are meshless methods, which are especially suitable for
handling irregular domain boundaries, as they can work on scattered nodes
making it easy to discretise complex geometries [7]. While there have already
been some successful attempts at modelling electromagnetic phenomena in the
scope of meshless methods [5, 6], none have really gained widespread use.

Despite that, we take yet another meshless approach to model the
electromagnetic fields. In particular, using the Radial Basis Function
Generated Finite Difference (RBF-FD) method we generalise the FDTD method.
After introducing our approach we investigate some of the obstacles
encountered in our further simulations.

More precisely, the paper is structured as follows: The following section
briefly lists the methods used including the original Yee’s algorithm and the
RBF-FD method. Afterwards, our test problem is presented in Section 3, while
the results are shown and discussed in Section 4.

##  II Methods

Time evolution of electromagnetic fields is governed by the Maxwell’s
equations

$\displaystyle\mu_{0}\frac{\partial H_{x}}{\partial t}=$
$\displaystyle-\frac{\partial E_{z}}{\partial y},$ (1)
$\displaystyle\mu_{0}\frac{\partial H_{y}}{\partial t}=$
$\displaystyle\frac{\partial E_{z}}{\partial x},$ (2)
$\displaystyle\varepsilon_{0}\frac{\partial E_{z}}{\partial t}=$
$\displaystyle\frac{\partial H_{y}}{\partial x}-\frac{\partial H_{x}}{\partial
y},$ (3)

where we have limited ourselves to two dimensions and the TMz (Transverse
Magnetic to the z direction) propagation mode meaning that only the
$H_{x},H_{y},E_{z}$ fields and their $(x,y)$ dependence need to be considered.
$\mu_{0}$ and $\varepsilon_{0}$ are the vacuum permeability and permittivity
respectively.

###  II-A The FDTD algorithm

As hinted already by its name, the FDTD algorithm is in essence just a finite
difference method - the partial derivatives appearing in Maxwell’s equations
are approximated with central differences, transforming them into a linear
system.

The component that sets the algorithm apart from the usual finite difference
methods is a particular way in which the space and time are discretised - the
Yee grid. We define, for indices $(n,i,j)$

$\displaystyle E_{z}^{n,i,j}$ $\displaystyle=E_{z}(t=n\Delta t,x=i\Delta
s,y=j\Delta s),$ (4) $\displaystyle H_{x}^{n,i,j}$
$\displaystyle=H_{x}((n-0.5)\Delta t,i\Delta s,(j+0.5)\Delta s),$ (5)
$\displaystyle H_{y}^{n,i,j}$ $\displaystyle=H_{y}((n-0.5)\Delta
t,(i+0.5)\Delta s,j\Delta s),$ (6)

where $\Delta t$ and $\Delta s$ are the chosen spacings in time and space
direction, respectively.

This allows us to discretise the Maxwell’s equations and get the explicit FDTD
update equations:

$\displaystyle H_{x}^{n+1,i,j}=H_{x}^{n,i,j}-\frac{\Delta t}{\mu_{0}\Delta s}$
$\displaystyle(E_{z}^{n,i,j+1}-E_{z}^{n,i,j}),$ (7) $\displaystyle
H_{y}^{n+1,i,j}=H_{y}^{n,i,j}+\frac{\Delta t}{\mu_{0}\Delta s}$
$\displaystyle(E_{z}^{n,i+1,j}-E_{z}^{n,i,j}),$ (8) $\displaystyle
E_{z}^{n+1,i,j}=E_{z}^{n,i,j}+\frac{\Delta t}{\varepsilon_{0}\Delta s}$
$\displaystyle(H_{y}^{n+1,i,j}-H_{y}^{n+1,i-1,j}$ $\displaystyle-$
$\displaystyle(H_{x}^{n+1,i,j}-H_{x}^{n+1,i,j-1})).$ (9)

The staggering of the Yee grid causes the above method to be of second order
in both space and time. A more detailed introduction to the FDTD method along
with the necessary prerequisite knowledge of finite differences and
electromagnetics can be found in [8].

###  II-B The RBF-FD Method

The RBF-FD method allows us to obtain an approximation for a given linear
differential operator $\mathcal{L}$ using only the positions of the
discretisation nodes $(x_{i},y_{i})_{i=1}^{N}$ without any additional
information about them. This is done by associating to each node
$(x_{i},y_{i})$ its stencil $S_{i}$ \- a set of nodes used for the
approximation, commonly taken to be its $ss$ (stencil size) nearest
neighbours. The operator acting on a function is then expressed as a linear
combination of function values in the stencil as

$\mathcal{L}f(x_{i},y_{i})\approx\sum_{j\in S_{i}}w_{j}f(x_{j},y_{j}),$ (10)

where the weights $w_{j}$ can be determined from the locations of the nodes
alone. The details exceed the scope of this paper and we refer the reader to
chapter 5 of [9].

###  II-C Our Meshless FDTD Generalisation

We now describe our attempt at generalising the FDTD method to a meshless
setting. The time coordinate has a simple geometry so we keep this part of the
FDTD and stagger the fields in time. The difference comes with how the spatial
derivatives are treated. There isn’t a clear way on how the spatial staggering
should be done if the nodes are allowed to be positioned artbitrary so we have
decided to abandon it and calculate both the $E$ and $H$ fields at the same
space points. This results in the following update equations

$\displaystyle H_{x}^{n+1}(x,y)=H_{x}^{n}(x,y)-\frac{\Delta t}{\mu_{0}}$
$\displaystyle\mathcal{L}_{y}(E_{z}^{n})(x,y),$ (11) $\displaystyle
H_{y}^{n+1}(x,y)=H_{y}^{n}(x,y)+\frac{\Delta t}{\mu_{0}}$
$\displaystyle\mathcal{L}_{x}(E_{z}^{n})(x,y),$ (12) $\displaystyle
E_{z}^{n+1}(x,y)=E_{z}^{n}(x,y)+\frac{\Delta t}{\varepsilon_{0}}($
$\displaystyle\mathcal{L}_{x}(H_{y}^{n+1})(x,y)$ $\displaystyle-$
$\displaystyle\mathcal{L}_{y}(H_{x}^{n+1})(x,y)),$ (13)

where $\mathcal{L}_{x}$ is a RBF-FD approximation of $\partial_{x}$ and
analogously for $\mathcal{L}_{y}$. RBF-FD requires us to make a choice of a
Radial Basis Function (RBF) to be used in the approximation. We employ the
Polyharmonic Splines (PHS) of degree $3$ as our RBF of choice, as they possess
no shape parameter, eliminating the additional work that would come with
determining its suitable value. Additionally, our approximation is augmented
by monomials up to degree $m=2$ inclusive, which causes the derivatives to be
second order accurate [10], as is the case in the FDTD. We start with a
minimal stencil size of $ss=6$, corresponding to a pure monomial approximation
[10].

##  III Problem setup

The considered problem is propagation of the electromagnetic field from a
single source in an otherwise empty medium (vacuum). The domain is a square
$1\leq i,j\leq 600$, where the discretisation distance is $\Delta s=1$. The
time step is given by the Courant limit $\Delta t=\frac{S_{c}\Delta
s}{c_{0}}$, where $c_{0}$ is the speed of light in the vacuum and $S_{c}$ is
the Courant number, taken to be $\frac{1}{\sqrt{2}}$ to minimise dispersion
[8].

Near the middle of the domain, we have a sinusoidal source:
$E_{z}^{n,300,300}=\sin\left(2\pi fn\right)$ with a frequency of $f=S_{c}/30$.
This is a hard source, meaning we manually set the field to this value after
each time step. The simulation will stop at $n=300$, which is before the waves
reach the boundary so we do not need to take any boundary effects into
account.

We will compare both the FDTD and our described method on this setup. While
meshless methods are usually not meant to be used on a grid, this is only to
test whether our RBF-FD formulation can replicate the correct physics. We
don’t expect more accurate results than those obtained by FDTD - the advantage
of our method would come from being able to operate on scattered nodes.

##  IV Results

Figure 1 shows the resulting simulations. A problem can immediately be
spotted: certain grid points are not updated properly and remain at their
initial value of zero, resulting in a checkerboard-like pattern.

The reason lies in the approximation of the spatial derivatives appearing in
Maxwell’s equations. As seen in Figure 2, RBF-FD with a stencil size of $ss=6$
replicates the ordinary central difference formulas for the first derivative.
These central differences are such that the derivative at given point
$(x_{i},y_{i})$ depends only on the function values at the neighbouring nodes,
not on the node $(x_{i},y_{i})$ itself. Plugging this into the update
equations for our case, it turns out that the values of $E_{z}$ at nodes, that
are an odd number of grid points away from the source in either the $x$ or $y$
direction, are never updated. A similar pattern arises for fields
$H_{x},H_{y}$.

If we consider only the fields that are getting updated (i.e. ignoring the
update equations for the irrelevant ones), we actually get a Yee grid with a
discretisation distance of $\Delta s=2$. This motivates us to repeat the
simulation with $\Delta s=0.5$ (while keeping the Courant number fixed) and
only plot the integer coordinates, hiding the nodes, which we know are not
updated properly. The resulting solution snapshots look much closer to the
ones given by the FDTD simulation. We have also numerically confirmed that we
do indeed get the same quantitative results as with the usual FDTD method.
Deviating from this setup in some way, such as by increasing the stencil size,
will therefore allow us to obtain generalised versions of the FDTD.

Figure 1: Solution snapshots for both the FDTD and RBF-FD methods. In the
$\Delta s=0.5$ case we have hidden the irrelevant nodes. A zoomed-in portion
of the snapshot is shown for the $n=100$ case.

Using a finer discretisation only to then throw out a big portion of the nodes
is computationally wasteful. One attempt to migitate this issue is to use non-
centered stencils, as then the algorithm will not reproduce the usual central
difference formulas. However, in this case a new problem arises - stability.
It is well known that in the FDTD method we require our time step to be
sufficiently small for a stable time evolution. A similar limitation also
holds for other choices of the solution procedures with different stability
conditions.

Figure 2: Different stencils and their corresponding stability limit Courant
numbers. The center node is marked with a square and the node colours
correspond to the RBF-FD weights $w_{y}$ for $\partial_{y}$.

In order to assess the stability of our method, we have performed the Von
Neumann stability analysis described in [8]. A plane wave ansatz
$E^{n}_{z}(x,y)=E^{n}_{z0}e^{i(k_{x}x+k_{y}y)}$ (and similarly for
$H_{x},H_{y}$) is plugged into our update equations to obtain a relation

$\begin{pmatrix}H^{n+1}_{x0}\\\ H^{n+1}_{y0}\\\
E^{n+1}_{z0}\end{pmatrix}=A\begin{pmatrix}H^{n}_{x0}\\\ H^{n}_{y0}\\\
E^{n}_{z0}\end{pmatrix}.$ (14)

We then check at which time step $\Delta t$ or, equivalently, at which Courant
number $S_{c}$, the spectral radius of the matrix $A$ (the magnitude of its
largest eigenvalue) exceeds $1$. This gives sufficient conditions for
stability.

The results can be seen in Figure 2, which shows that the considered
asymmetric stencils are unstable. An exception is the case of $ss=6$, where
the node that is ruining the symmetry has a zero weight effectively making the
stencil symmetric. Note that this is the previously mentioned case of RBF-FD
reproducing the central difference formulas.

Overcoming the stability issue is not at all trivial and will require a lot of
care when attempting to use the RBF-FD method for different stencils,
especially in the case of scattered nodes, where many possible stencil shapes
can arise of varying regularity. This is a whole topic of its own and we have
not delved into it any further at this time. Instead, we look at the behaviour
of the method for stencil sizes above the minimal $ss=6$ case that are still
stable: $ss=9,13,25$111while the $ss=25$ case is not covered in Figure 2, it
is a symmetric stencil and turns out to be stable..

These stencils are centered and turn out to also exhibit checkerboard-like
patterns. So for the purpose of visualisation we again set $\Delta s=0.5$ and
only display the integer coordinates. We continue to simulate at
$S_{c}=\frac{1}{\sqrt{2}}$, but we have checked that the following
observations occur also for different time steps. Figure 3 shows the results
and highlights another important issue - dispersion. The simulation fails to
produce the correct physics as some superluminal modes start propagating. This
can be concisely seen in the Fourier space: Considering the solution slice
$E_{z}(n,i,j=300)$ and performing the 2D Fourier transform we can see that the
$ss=6$ (or equivalently, FDTD) case only has a single mode present (i.e. a
single peak in the Fourier space), centered at the Fourier component that is
propagating at the speed of light. On the other hand, for $ss>6$ multiple
modes are present, seen as multiple peaks in the Fourier space of various
width and intensity, some of them propagating at speeds faster than the speed
of light. The simulation was run until $n=300$ and the time direction was
windowed with a Hann function before performing the Fourier transform. The
displayed Fourier space plots are zoomed in, as the magnitude of the
components not displayed was neglible. The Fourier transform convention used
is $A_{k}=\sum_{m=0}^{N-1}a_{m}\exp(-2\pi i\ mk/N)$.

As a closing remark, it must be mentioned that the analysis here has been
limited to a very special case of the hard source defined at a single point
and the observations made are not general. Nevertheless, the problem
considered turned out to be a suitable playground for the investigated method,
as it was simple to implement and managed to highlight some shortcomings of
our generalisation.

Figure 3: Solution snapshots at $n=150$ and the normalised Fourier component
magnitudes, plotted for various stencil sizes. $\omega$ and $k$ are the
temporal and spatial frequency indices respectively. The speed of light is
shown with a black line.

##  V Conclusions

We have presented an attempt to generalise the FDTD method to a meshless
setting, replacing its spatial derivatives by the appropriate RBF-FD
approximations. Testing the method on the grid, we verified that this really
is a generalisation - for the lowest possible stencil size we are able to
reproduce the FDTD. We pointed out two major obstacles encountered in our
generalisation - dispersion and stability. These are stencil-dependent
properties and therefore especially important to understand in scattered node
scenarios, where the shapes of stencils are less regular. In this context our
paper serves as a basic, but necessary step towards developing a robust,
adaptive scheme for solving electromagnetic problems meshlessly. A sensible
continuation of this research is a focus on lowering the degree of dispersion
or increasing the stability of the procedure, either by a careful selection of
the stencils or an appropriate modification of our method.

## References

  * [1] K. Yee, “Numerical solution of initial boundary value problems involving maxwell’s equations in isotropic media,” _IEEE Transactions on antennas and propagation_ , vol. 14, no. 3, pp. 302–307, 1966.
  * [2] M. Brio, J. Moloney, and A. Zakharian, “Fdtd based second-order accurate local mesh refinement method for maxwell’s equations in two space dimensions,” _Communications in Mathematical Sciences_ , vol. 2, no. 3, pp. 497–513, 2004\.
  * [3] K. S. Yee and J. S. Chen, “Conformal hybrid finite difference time domain and finite volume time domain,” _IEEE transactions on antennas and propagation_ , vol. 42, no. 10, pp. 1450–1455, 1994.
  * [4] J. S. Hesthaven and T. Warburton, “Nodal high-order methods on unstructured grids: I. time-domain solution of maxwell’s equations,” _Journal of Computational Physics_ , vol. 181, no. 1, pp. 186–221, 2002.
  * [5] M. Dehghan and R. Salehi, “A meshless local petrov–galerkin method for the time-dependent maxwell equations,” _Journal of Computational and Applied Mathematics_ , vol. 268, pp. 93–110, 2014.
  * [6] S. Lai, B. Wang, and Y. Duan, “Meshless radial basis function method for transient electromagnetic computations,” _IEEE Transactions on Magnetics_ , vol. 44, no. 10, pp. 2288–2295, 2008.
  * [7] J. Slak and G. Kosec, “On generation of node distributions for meshless pde discretizations,” _SIAM journal on scientific computing_ , vol. 41, no. 5, pp. A3202–A3229, 2019.
  * [8] R. A. M. Umran S. Inan, _Numerical Electromagnetics: The FDTD Method_ , 1st ed. Cambridge University Press, 2011\.
  * [9] B. Fornberg and N. Flyer, _A Primer on Radial Basis Functions with Applications to the Geosciences_ , ser. CBMS-NSF Regional Conference Series in Applied Mathematics 87. SIAM, 2015.
  * [10] V. Bayona, “An insight into rbf-fd approximations augmented with polynomials,” _Computers & Mathematics with Applications_, vol. 77, no. 9, pp. 2337–2353, 2019.


# Three-chromatic geometric hypergraphs

Gábor Damásdi
MTA-ELTE Lendület
Combinatorial Geometry Research Group  Dömötör Pálvölgyi
MTA-ELTE Lendület
Combinatorial Geometry Research Group

###### Abstract

We prove that for any planar convex body $C$ there is a positive integer $m$
with the property that any finite point set $P$ in the plane can be three-
colored such that there is no translate of $C$ containing at least $m$ points
of $P$, all of the same color. As a part of the proof, we show a strengthening
of the Erdős-Sands-Sauer-Woodrow conjecture. Surprisingly, the proof also
relies on the two dimensional case of the Illumination conjecture.

##  1 Introduction

Our main result is the following.

######  Theorem 1.

For any planar convex body $C$ there is a positive integer $m=m(C)$ such that
any finite point set $P$ in the plane can be three-colored in a way that there
is no translate of $C$ containing at least $m$ points of $P$, all of the same
color.

This result closes a long line of research about coloring points with respect
to planar range spaces that consist of translates of a fixed set, a problem
that was proposed by Pach over forty years ago [23]. In general, a pair
$(P,{\mathcal{S}})$, where $P$ is a set of points in the plane and
${\mathcal{S}}$ is a family of subsets of the plane, called the _range space_
, defines a _primal_ hypergraph ${\mathcal{H}}(P,{\mathcal{S}})$ whose vertex
set is $P$, and for each $S\in{\mathcal{S}}$ we add the edge $S\cap P$ to the
hypergraph. Given any hypergraph ${\mathcal{H}}$, a planar realization of
${\mathcal{H}}$ is defined as a pair $(P,{\mathcal{S}})$ for which
${\mathcal{H}}(P,{\mathcal{S}})$ is isomorphic to ${\mathcal{H}}$. If
${\mathcal{H}}$ can be realized with some pair $(P,{\mathcal{S}})$ where
${\mathcal{S}}$ is from some family ${\mathcal{F}}$, then we say that
${\mathcal{H}}$ is realizable with ${\mathcal{F}}$. The dual of the hypergraph
${\mathcal{H}}(P,{\mathcal{S}})$, where the elements of the range space
${\mathcal{S}}$ are the vertices and the points $P$ define the edges, is known
as the _dual_ hypergraph and is denoted by ${\mathcal{H}}({\mathcal{S}},P)$.
If ${\mathcal{H}}={\mathcal{H}}({\mathcal{S}},P)$ where ${\mathcal{S}}$ is
from some family ${\mathcal{F}}$, then we say that ${\mathcal{H}}$ has a dual
realization with ${\mathcal{F}}$. Pach observed [23, 26] that if
${\mathcal{F}}$ is the family of translates of some set, then ${\mathcal{H}}$
has a dual realization with ${\mathcal{F}}$ if and only if ${\mathcal{H}}$ has
a (primal) realization with ${\mathcal{F}}$.

Pach proposed to study the chromatic number of hypergraphs realizable with
different geometric families ${\mathcal{F}}$. It is important to distinguish
between two types of hypergraph colorings that we will use, the _proper_
coloring and the _polychromatic_ coloring.

######  Definition 2.

A hypergraph is _properly $k$-colorable_ if its vertices can be colored with
$k$ colors such that each edge contains points from at least two color
classes. Such a coloring is called a _proper $k$-coloring_. If a hypergraph
has a proper $k$-coloring but not a proper $(k-1)$-coloring, then it is called
_$k$ -chromatic_.

A hypergraph is _polychromatic $k$-colorable_ if its vertices can be colored
with $k$ colors such that each edge contains points from each color class.
Such a coloring is called a _polychromatic $k$-coloring_.

Note that for a polychromatic $k$-coloring to exist, it is necessary that each
edge of the underlying hypergraph has at least $k$ vertices. More generally,
we say that a hypergraph is _$m$ -heavy_ if each of its edges has at least $m$
vertices.

The main question that Pach raised can be rephrased as follows.

######  Question 3.

For which planar families ${\mathcal{F}}$ is there an
$m_{k}=m({\mathcal{F}},k)$ such that any $m_{k}$-heavy hypergraph realizable
with ${\mathcal{F}}$ has a proper/polychromatic $k$-coloring?

Initially, this question has been mainly studied for polychromatic
$k$-colorings (known in case of a dual range space as _cover-decomposition_
problem), and it was shown that such an $m_{k}$ exists if ${\mathcal{F}}$ is
the family of translates of some convex polygon [24, 34, 30], or the family of
all halfplanes [16, 33], or the homothetic111A _homothetic copy_ , or
_homothet_ , is a scaled and translated (but non-rotated) copy of a set. We
always require the scaling factor to be positive. Note that this is sometimes
called a positive homothet. copies of a triangle [17] or of a square [2],
while it was also shown that not even $m_{2}$ exists if ${\mathcal{F}}$ is the
family of translates of some appropriate concave polygon [27, 29] or any
body222By _body_ , we always mean a compact subset of the plane with a non-
empty interior, though our results (and most of the results mentioned) also
hold for sets that are unbounded, or that contain an arbitrary part of their
boundary, and are thus neither open, nor closed. This is because a realization
of a hypergraph can be perturbed slightly to move the points off from the
boundaries of the sets realizing the respective edges of the hypergraph. with
a smooth boundary [25]. It was also shown that there is no $m_{k}$ for proper
$k$-colorings if ${\mathcal{F}}$ is the family of all lines [27] or all axis-
parallel rectangles [11]; for these families, the same holds in case of dual
realizations [27, 28]. For homothets of convex polygons other than triangles,
it is known that there is no $m_{2}$ for dual realizations [21], unlike for
primal realizations. Higher dimensional variants [17, 10] and improved bounds
for $m_{k}$ have been also studied [4, 15, 9, 18, 5, 8]. For other results,
see also the decade old survey [26], or the up-to-date website
https://coge.elte.hu/cogezoo.html.

If ${\mathcal{F}}$ is the translates or homothets of some planar convex body,
it is an easy consequence of the properties of generalized Delaunay-
triangulations and the Four Color Theorem that any hypergraph realizable with
${\mathcal{F}}$ is proper 4-colorable if every edge contains at least two
vertices. We have recently shown that this cannot be improved for homothets.

######  Theorem 4 (Damásdi, Pálvölgyi [12]).

Let $C$ be any convex body in the plane that has two parallel supporting lines
such that $C$ is strictly convex in some neighborhood of the two points of
tangencies. For any positive integer $m$, there exists a 4-chromatic
$m$-uniform hypergraph that is realizable with homothets of $C$.

For translates, we recall the following result.

######  Theorem 5 (Pach, Pálvölgyi [25]).

Let $C$ be any convex body in the plane that has two parallel supporting lines
such that $C$ is strictly convex in some neighborhood of the two points of
tangencies.333This condition can be relaxed to require only one smooth
neighborhood on the boundary. Since this is not the main topic of our paper,
we just give a sketch of the construction in Appendix B. For any positive
integer $m$, there exists a 3-chromatic $m$-uniform hypergraph that is
realizable with translates of $C$.

This left only the following question open: Is there for any planar convex
body $C$ a positive integer $m$ such that that no 4-chromatic $m$-uniform
hypergraph is realizable with translates of $C$? Our Theorem 1 answers this
question affirmatively for all $C$ by showing that all realizable $m$-heavy
hypergraphs are three-colorable for some $m$. This has been hitherto known to
hold only when $C$ is a polygon (in which case 2 colors suffice [30], and 3
colors are known to be enough even for homothets [19]) and pseudodisk families
that intersect in a common point [1] (which generalizes the case when $C$ is
unbounded, in which case 2 colors suffice [25]).

Note that the extended abstract of our first proof attempt appeared recently
in the proceedings of EuroComb 2021 [13]. That proof, however, only worked
when $C$ was a disk, and while the generalization to other convex bodies with
a smooth boundary seemed feasible, we saw no way to extend it to arbitrary
convex bodies. The proof of Theorem 1 relies on a surprising connection to two
other famous results, the solution of the two dimensional case of the
Illumination conjecture [22], and a recent solution of the Erdős-Sands-Sauer-
Woodrow conjecture by Bousquet, Lochet and Thomassé [7]. In fact, we need a
generalization of the latter result, which we prove with the addition of one
more trick to their method; this can be of independent interest.

The rest of the paper is organized as follows.
In Section 2 we present the three main ingredients of our proof:

  * •

the Union Lemma (Section 2.1),

  * •

the Erdős-Sands-Sauer-Woodrow conjecture (Section 2.2)—the proof of our
generalization of the Bousquet-Lochet-Thomassé theorem can be found in
Appendix A,

  * •

the Illumination conjecture (Section 2.3), which is a theorem of Levi in the
plane.

In Section 3 we give the detailed proof of Theorem 1.
In Section 4 we give a general overview of the steps of the algorithm
requiring computation to show that we can find a three-coloring in randomized
polynomial time.
Finally, in Section 5, we pose some problems left open.

##  2 Tools

###  2.1 Union Lemma

Polychromatic colorability is a much stronger property than proper
colorability. Any polychromatic $k$-colorable hypergraph is proper
$2$-colorable. We generalize this trivial observation to the following
statement about unions of polychromatic $k$-colorable hypergraphs.

######  Lemma 6 (Union Lemma).

Let ${\mathcal{H}}_{1}=(V,E_{1}),\dots,{\mathcal{H}}_{k-1}=(V,E_{k-1})$ be
hypergraphs on a common vertex set $V$. If
${\mathcal{H}}_{1},\dots,{\mathcal{H}}_{k-1}$ are polychromatic $k$-colorable,
then the hypergraph
$\bigcup\limits_{i=1}^{k-1}{\mathcal{H}}_{i}=(V,\bigcup\limits_{i=1}^{k-1}E_{i})$
is proper $k$-colorable.

###### Proof.

Let $c_{i}:V\rightarrow\\{1,\ldots,k\\}$ be a polychromatic $k$-coloring of
${\mathcal{H}}_{i}$. Choose $c(v)\in\\{1,\ldots,k\\}$ such that it differs
from each $c_{i}(v)$. We claim that $c$ is a proper $k$-coloring of
$\bigcup\limits_{i=1}^{k-1}{\mathcal{H}}_{i}$. To prove this, it is enough to
show that for every edge $H\in{\mathcal{H}}_{i}$ and for every color
$j\in\\{1,\ldots,k-1\\}$, there is a $v\in H$ such that $c(v)\neq j$. We can
pick $v\in H$ for which $c_{i}(v)=j$. This finishes the proof. ∎

Lemma 6 is sharp in the sense that for every $k$ there are $k-1$ hypergraphs
such that each is polychromatic $k$-colorable but their union is not properly
$(k-1)$-colorable.

We will apply the Union Lemma combined with the theorem below. A _pseudoline
arrangement_ is a collection of simple curves, each of which splits
$\mathbb{R}^{2}$ into two unbounded parts, such that any two curves intersect
at most once. A _pseudohalfplane_ is the region on one side of a pseudoline in
such an arrangement. For hypergraphs realizible by pseudohalfplanes the
following was proved, generalizing a result of Smorodinsky and Yuditsky [33]
about halfplanes.

######  Theorem 7 (Keszegh-Pálvölgyi [20]).

Any $(2k-1)$-heavy hypergraph realizable by pseudohalfplanes is polychromatic
$k$-colorable, i.e., given a finite set of points and a pseudohalfplane
arrangement in the plane, the points can be $k$-colored such that every
pseudohalfplane that contains at least $2k-1$ points contains all $k$ colors.

Combining Theorem 7 with Lemma 6 for $k=3$, we obtain the following.

######  Corollary 8.

Any $5$-heavy hypergraph realizable by two pseudohalfplane families is proper
$3$-colorable, i.e., given a finite set of points and two different
pseudohalfplane arrangements in the plane, the points can be $3$-colored such
that every pseudohalfplane that contains at least $5$ points contains two
differently colored points.

###  2.2 Erdős-Sands-Sauer-Woodrow conjecture

Given a quasi order444A quasi order $\prec$ is a reflexive and transitive
relation, but it is not required to be antisymmetric, so $p\prec q\prec p$ is
allowed, unlike for partial orders. $\prec$ on a set $V$, we interpret it as a
digraph $D=(V,A)$, where the vertex set is $V$ and a pair $(x,y)$ defines an
arc in $A$ if $x\prec y$. The _closed in-neighborhood_ of a vertex $x\in V$ is
$N^{-}(x)=\\{x\\}\cup\\{y|(y,x)\in A\\}$. Similarly the _closed out-
neighborhood_ of a vertex $x$ is $N^{+}(x)=\\{x\\}\cup\\{y|(x,y)\in A\\}$. We
extend this to subsets $S\subset V$ as $N^{-}(S)=\bigcup\limits_{x\in
S}N^{-}(x)$ and $N^{+}(S)=\bigcup\limits_{x\in S}N^{+}(x)$. A set of vertices
$S$ such that $N^{+}(S)=V$ is said to be _dominating_. For $A,B\subset V$ we
will also say that _$A$ dominates $B$ _ if $B\subset N^{+}(A)$.

A _complete multidigraph_ is a digraph where parallel edges are allowed and in
which there is at least one arc between each pair of distinct vertices. Let
$D$ be a complete multidigraph whose arcs are the disjoint union of $k$ quasi
orders $\prec_{1},\dots,\prec_{k}$ (parallel arcs are allowed). Define
$N^{-}_{i}(x)$ (resp. $N^{+}_{i}(x)$) as the closed in-neighborhood (resp.
out-neighborhood) of the digraph induced by $\prec_{i}$.

Proving a conjecture of Erdős, and of Sands, Sauer and Woodrow [32], Bousquet,
Lochet and Thomassé recently showed the following.

######  Theorem 9 (Bousquet, Lochet, Thomassé [7]).

For every $k$, there exists an integer $f(k)$ such that if $D$ is a complete
multidigraph whose arcs are the union of $k$ quasi orders, then $D$ has a
dominating set of size at most $f(k)$.

We show the following generalization of Theorem 9.

######  Theorem 10.

For every pair of positive integers $k$ and $l$, there exist an integer
$f(k,l)$ such that if $D=(V,A)$ is a complete multidigraph whose arcs are the
union of $k$ quasi orders $\prec_{1},\dots,\prec_{k}$, then $V$ contains a
family of pairwise disjoint subsets $S_{i}^{j}$ for $i\in[k]$, $j\in[l]$ with
the following properties:

  * •

$|\bigcup\limits_{i,j}S_{i}^{j}|\leq f(k,l)$

  * •

For each vertex $v\in V\setminus\bigcup\limits_{i,j}S_{i}^{j}$ there is an
$i\in[k]$ such that for each $j\in[l]$ there is an edge of $\prec_{i}$ from a
vertex of $S_{i}^{j}$ to $v$.

Note that disjointness is the real difficulty here, without it the theorem
would trivially hold from repeated applications of Theorem 9. We saw no way to
derive Theorem 10 from Theorem 9, but with an extra modification the proof
goes through. The full proof of Theorem 10 can be found in Appendix A.

###  2.3 Hadwiger’s Illumination conjecture and pseudolines

Hadwiger’s Illumination conjecture has a number of equivalent formulations and
names.555These include names such as Levi–Hadwiger Conjecture, Gohberg–Markus
Covering Conjecture, Hadwiger Covering Conjecture, Boltyanski–Hadwiger
Illumination Conjecture. For a recent survey, see [6]. We will use the
following version of the conjecture.

Let $\mathbb{S}^{d-1}$ denote the unit sphere in $\mathbb{R}^{d}$. For a
convex body $C$, let $\partial C$ denote the boundary of $C$ and let $int(C)$
denote its interior. A direction $u\in\mathbb{S}^{d-1}$ _illuminates_
$b\in\partial C$ if $\\{b+\lambda u:\lambda>0\\}\cap int(C)\neq\emptyset$.

######  Conjecture 11.

The boundary of any convex body in $\mathbb{R}^{d}$ can be illuminated by
$2^{d}$ or fewer directions. Furthermore, the $2^{d}$ lights are necessary if
and only if the body is a parallelepiped.

The conjecture is open in general. The $d=2$ case was settled by Levi [22] in
1955. For $d=3$ the best result is due to Papadoperakis [31], who showed that
16 lights are enough.

In the following part we make an interesting connection between the
Illumination conjecture and pseudolines. Roughly speaking, we show that the
Illumination conjecture implies that for any convex body in the plane the
boundary can be broken into three parts such that the translates of each part
behave similarly to pseudolines, i.e., we get three pseudoline arrangements
from the translates of the three parts.

To put this into precise terms, we need some technical definitions and
statements. Fix a body $C$ and an injective parametrization of $\partial C$,
$\gamma:[0,1]\rightarrow\partial C$, that follows $\partial C$
counterclockwise. For each point $p$ of $\partial C$ there is a set of
possible tangents touching at $p$. Let $g(p)\subset\mathbb{S}^{1}$ denote the
Gauss image of $p$, i.e., $g(p)$ is the set of unit outernormals of the
tangent lines touching at $p$. Note that $g(p)$ is an arc of $\mathbb{S}^{1}$
and $g(p)$ is a proper subset of $\mathbb{S}^{1}$.

Let $g_{+}:\partial C\rightarrow\mathbb{S}^{1}$ be the function that assigns
to $p$ the counterclockwise last element of $g(p)$. (See Figure 1 left.)
Similarly let $g_{-}$ be the function that assigns to $p$ the clockwise last
element of $g(p)$. Thus, $g(p)$ is the arc from $g_{-}(p)$ to $g_{+}(p)$. Let
$|g(p)|$ denote the length of $g(p)$.

$p$$g_{-}(p)$$g_{+}(p)$

$p$$q$$J_{2}$$J_{1}$

Figure 1: Extremal tangents at a boundary point (on the left) and parallel
tangents on two intersecting translates (on the right).

######  Observation 12.

$g_{+}\circ\gamma$ is continuous from the right and $g_{-}\circ\gamma$ is
continuous from the left.

For $t_{1}<t_{2}$ let $\gamma_{[t_{1},t_{2}]}$ denote the restriction of
$\gamma$ to the interval $[t_{1},t_{2}]$. For $t_{1}>t_{2}$ let
$\gamma_{[t_{1},t_{2}]}$ denote the concatenation of $\gamma_{[t_{1},1]}$ and
$\gamma_{[0,t_{2}]}$. When it leads to no confusion, we identify
$\gamma_{[t_{1},t_{2}]}$ with its image, which is a connected part of the
boundary $\partial C$. For such a $J=\gamma_{[t_{1},t_{2}]}$, let
$g(J)=\bigcup\limits_{p\in J}g(p)$. Clearly, $g(J)$ is an arc of
$\mathbb{S}^{1}$ from $g_{-}(t_{1})$ to $g_{+}(t_{2})$; let $|g(J)|$ denote
the length of this arc.

######  Lemma 13.

Let $C$ be a convex body and assume that $J$ is a connected part of $\partial
C$ such that $|g(J)|<\pi$. Then there are no two translates of $J$ that
intersect in more than one point.

###### Proof.

Suppose $J$ has two translates $J_{1}$ and $J_{2}$ such that they intersect in
two points, $p$ and $q$. Now both $J_{1}$ and $J_{2}$ has a tangent that is
parallel to the segment $pq$. (See Figure 1 right.) This shows that $J$ has
two different tangents parallel to $pq$ and therefore $g(J)\geq\pi$. ∎

######  Lemma 14.

For a convex body $C$, which is not a parallelogram, and an injective
parametrization $\gamma$ of $\partial C$, we can pick $0\leq
t_{1}<t_{2}<t_{3}\leq 1$ such that
$|g(\gamma_{[t_{1},t_{2}]})|,|g(\gamma_{[t_{2},t_{3}]})|$ and
$|g(\gamma_{[t_{3},t_{1}]})|$ are each strictly smaller than $\pi$.

###### Proof.

We use the 2-dimensional case of the Illumination conjecture (proved by Levi
[22]). If $C$ is not a parallelogram, we can pick three directions,
$u_{1},u_{2}$ and $u_{3}$, that illuminate $C$. Pick $t_{1}$ such that
$\gamma(t_{1})$ is illuminated by both $u_{1}$ and $u_{2}$. To see why this is
possible, suppose that the parts illuminated by $u_{1}$ and $u_{2}$ are
disjoint. Each light illuminates a continuous open ended part of the boundary.
So in this case there are two disjoint parts of the boundary that are not
illuminated. If $u_{3}$ illuminates both, then it illuminates everything that
is illuminated by $u_{1}$ or everything that is illuminated by $u_{2}$. But
two lights are never enough for illumination, a contradiction.

Using the same argument, pick $t_{2}$ and $t_{3}$ such that $\gamma(t_{2})$ is
illuminated by both $u_{2}$ and $u_{3}$ and $\gamma(t_{3})$ is illuminated by
both $u_{3}$ and $u_{1}$.

Note that $u_{1}$ illuminates exactly those points for which
$g_{+}(p)<u_{1}+\pi/2$ and $g_{-}(p)>u_{1}-\pi/2$. Therefore,
$|g(\gamma_{[t_{1},t_{3}]})|<u_{1}+\pi/2-(u_{1}-\pi/2)=\pi$. Similarly
$|g(\gamma_{[t_{1},t_{2}]})|<\pi$ and $|g(\gamma_{[t_{2},t_{3}]})|<\pi$. ∎

Observation 12 and Lemma 14 immediately imply the following statement.

######  Lemma 15.

For a convex body $C$, which is not a parallelogram, and an injective
parametrization $\gamma$ of $\partial C$, we can pick $0\leq
t_{1}<t_{2}<t_{3}\leq 1$ and $\varepsilon>0$ such that
$|g(\gamma_{[t_{1}-\varepsilon,t_{2}+\varepsilon]})|$,
$|g(\gamma_{[t_{2}-\varepsilon,t_{3}+\varepsilon]})|$ and
$|g(\gamma_{[t_{3}-\varepsilon,t_{1}+\varepsilon]})|$ are each strictly
smaller than $\pi$.

##  3 Proof of Theorem 1

###  3.1 Quasi orderings on planar point sets

Cones provide a natural way to define quasi orderings on point sets (see [34]
for an example where this idea was used). A _cone_ is a closed region in the
plane that is bounded by two rays that emanate from the origin. For a cone $K$
let $-K$ denote the cone that is the reflection of $K$ across the origin and
let $p+K$ denote the translate of $K$ by the vector $p$.

######  Observation 16.

For any $p,q\in\mathbb{R}^{2}$ and cone $K$, the following are equivalent (see
Figure 2):

  * •

$p\in q+K$

  * •

$q\in p+(-K)$

  * •

$p+K\subset q+K$

$q$$p$$p$$q$

Figure 2: Basic properties of cones.

For a cone $K$ let $\prec_{K}$ denote the quasi ordering on the points of the
plane where a point $p$ is bigger than a point $q$ if and only if $p+K$
contains $q$, i.e., when interpreted as a digraph, $qp$ is an edge of
$\prec_{K}$. By Observation 16, this ordering is indeed transitive.

Figure 3: Quasi orderings on a point set.

Suppose the cones $K_{1},K_{2},K_{3}$ correspond to the three corners of a
triangle, in other words the cones $K_{1},-K_{3},K_{2},-K_{1},K_{3},-K_{2}$
partition the plane around the origin in this order. Then we will say that
$K_{1},K_{2},K_{3}$ is a _set of tri-partition_ cones. In this case the
intersection of any translates of $K_{1},K_{2},K_{3}$ forms a (sometimes
degenerate) triangle.

######  Observation 17.

Let $K_{1},K_{2},K_{3}$ be a set of tri-partition cones and let $P$ be a
planar point set. Then any two distinct points of $P$ are comparable in either
$\prec_{K_{1}}$, $\prec_{K_{2}}$ or $\prec_{K_{3}}$. (See Figure 3.)

In other words, when interpreted as digraphs, the union of $\prec_{K_{1}}$,
$\prec_{K_{2}}$ and $\prec_{K_{3}}$ forms a complete multidigraph on $P$. As a
warm up for the proof of Theorem 1, we show the following theorem.

######  Theorem 18.

There exists a positive integer $m$ such that for any point set $P$, and any
set of tri-partition cones $K_{1},K_{2},K_{3}$, we can three-color $P$ such
that no translate of $K_{1}$, $K_{2}$ or $K_{3}$ that contains at least $m$
points of $P$ is monochromatic.

###### Proof.

We set $m$ to be $f(3,2)+13$ according to Theorem 10. Consider the three quasi
orders $\prec_{K_{1}}$, $\prec_{K_{2}}$ or $\prec_{K_{3}}$. Their union gives
a complete multidigraph on $P$, hence we can apply Theorem 10 with $k=3$ and
$l=2$, resulting in subsets $S_{i}^{j}$ for $i\in[3],j\in[2]$. Let
$S=\bigcup\limits_{i\in[3],j\in[2]}S_{i}^{j}$. For each point $p\in P\setminus
S$ there is an $i$ such that $\prec_{K_{i}}$ has an edge from a vertex of
$S_{i,1}$ and $S_{i,2}$ to $p$. Let $P_{1},P_{2},P_{3}$ be the partition of
$P\setminus S$ according to this $i$ value.

We start by coloring the points of $S$. Color the points of $S_{1,1}\cup
S_{2,1}\cup S_{3,1}$ with the first color and color the points of $S_{1,2}\cup
S_{2,2}\cup S_{3,2}$ with the second color.

Any translate of $K_{1}$, $K_{2}$ or $K_{3}$ that contains $f(3,2)+13$ points
of $P$, must contain $5$ points from either $P_{1},P_{2}$ or $P_{3}$ by the
pigeonhole principle. (Note that the cone might contain all points of $S$.)
Therefore, it is enough to show that for each $i\in[3]$ the points of $P_{i}$
can be three-colored such that no translate of $K_{1}$, $K_{2}$, or $K_{3}$
that contains at least $5$ points of $P_{i}$ is monochromatic.

Consider $P_{1}$; the proof is the same for $P_{2}$ and $P_{3}$. Take a
translate of $K_{1}$ and suppose that it contains a point $p$ of $P_{1}$. By
Theorem 10, there is and edge of $\prec_{K_{1}}$ from a vertex of $S_{1,1}$ to
$p$ and another edge from a vertex of $S_{1,2}$ to $p$. Thus any such
translate contains a point from $S_{1,1}$ and another point from $S_{1,2}$,
and hence it cannot be monochromatic.

Therefore, we only have to consider the translates of $K_{2}$ and $K_{3}$. Two
translates of a cone intersect at most once on their boundary. Hence, the
translates of $K_{2}$ form a pseudohalfplane arrangement, and so do the
translates of $K_{3}$. Therefore, by Corollary 8, there is a proper three-
coloring for the translates of $K_{2}$ and $K_{3}$ together. ∎

######  Remark 19.

From Theorem 18, it follows using standard methods (see Section 3.2) that
Theorem 1 holds for triangles. This was of course known before, even for two-
colorings of homothetic copies of triangles. Our proof cannot be modified for
homothets, but a two-coloring would follow if instead of Corollary 8 we
applied a more careful analysis for the two cones.

###  3.2 Proof of Theorem 1

If $C$ is a parallelogram, then our proof method fails. Luckily, translates of
parallelograms (and other symmetric polygons) were the first for which it was
shown that even two colors are enough [24]; in fact, by now we know that two
colors are enough even for homothets of parallelograms [2]. So from now on we
assume that $C$ is not a parallelogram.

The proof of Theorem 1 relies on the same ideas as we used for Theorem 18. We
partition $P$ into several parts, and for each part $P_{i}$, we divide the
translates of $C$ into three families such that two of the families each form
a pseudohalfplane arrangement over $P_{i}$, while the third family will only
contain translates that are automatically non-monochromatic. Then Corollary 8
would provide us a proper three-coloring. As in the proof of Theorem 18, this
is not done directly. First, we divide the plane using a grid, and then in
each small square we will use Theorem 10 to discard some of the translates of
$C$ at the cost of a bounded number of points.

The first step of the proof is a classic divide and conquer idea [24]. We
chose a constant $r=r(C)$ depending only on $C$ and divide the plane into a
grid of squares of side length $r$. Since each translate of $C$ intersects
some bounded number of squares, by the pidgeonhole principle we can find for
any positive integer $m$ another integer $m^{\prime}$ such that the following
holds: each translate $\hat{C}$ of $C$ that contains at least $m^{\prime}$
points intersects a square $Q$ such that $\hat{C}\cap Q$ contains at least $m$
points. For example, choosing $m^{\prime}=m(diam(C)/r+2)^{2}$ is sufficient,
where $diam(C)$ denotes the diameter of $C$. Therefore, it is enough to show
the following localized version of Theorem 1, since applying it separately for
the points in each square of the grid provides a proper three-coloring of the
whole point set.

######  Theorem 20.

There is a positive integer $m$ such that for any convex body $C$ there is a
positive real $r$ such that any finite point set $P$ in the plane that lies in
a square of side length $r$ can be three-colored in a way that there is no
translate of $C$ containing at least $m$ points of $P$, all of the same color.

We will show that $m$ can be chosen to be $f(3,2)+13$ according to Theorem 10,
independently of $C$.

###### Proof.

We pick $r$ the following way. First we fix an injective parametrization
$\gamma$ of $\partial C$ and then fix $t_{1},t_{2},t_{3}$ and $\varepsilon$
according to Lemma 15. Let $\ell_{1},\ell_{2},\ell_{3}$ be the tangents of $C$
touching at $\gamma(t_{1}),\gamma(t_{2})$ and $\gamma(t_{3})$. Let $K_{1,2}$,
$K_{2,3}$, $K_{3,1}$ be the set of tri-partition cones bordered by
$\ell_{1},\ell_{2},\ell_{3}$, such that $K_{i,i+1}$ is bordered by $\ell_{i}$
on its counterclockwise side, and by $\ell_{i+1}$ on its clockwise side (see
Figure 4 left, and note that we always treat $3+1$ as 1 in the subscript).

For a translate $\hat{C}$ of $C$ we will denote by $\hat{\gamma}$ the
translated parametrization of $\partial\hat{C}$, i.e.,
$\hat{\gamma}(t)=\gamma(t)+v$ if $\hat{C}$ was translated by vector $v$. Our
aim is to choose $r$ small enough to satisfy the following two properties for
each $i\in[3]$.

  1. (A)

Let $\hat{C}$ be a translate of $C$, and $Q$ be a square of side length $r$
such that $\partial\hat{C}\cap
Q\subset\hat{\gamma}_{[t_{i}+\varepsilon/2,t_{i+1}-\varepsilon/2]}$ (see
Figure 4 right). Then for any translate $K$ of $K_{i,i+1}$ whose apex is in
$Q\cap\hat{C}$, we have $K\cap Q\subset\hat{C}$. (I.e., $r$ is small with
respect to $C$.)

  2. (B)

Let $\hat{C}$ be a translate of $C$, and $Q$ be a square of side length $r$
such that $\hat{\gamma}_{[t_{i}-\varepsilon/2,t_{i+1}+\varepsilon/2]}$
intersects $Q$. Then $\partial\hat{C}\cap
Q\subset\hat{\gamma}_{[t_{i}-\varepsilon,t_{i+1}+\varepsilon]}$. (I.e., $r$ is
small compared to $\varepsilon$.)

$\ell_{1}$$\ell_{2}$$C$$\ell_{3}$$K_{3,1}$$K_{1,2}$$K_{2,3}$

$\hat{\gamma}(t_{1})$$\hat{\gamma}(t_{2})$$\ell_{1}$$\ell_{2}$$\hat{\gamma}(t_{2}-\varepsilon/2)$$\hat{\gamma}(t_{1}+\varepsilon/2)$$K$

Figure 4: Selecting the cones (on the left) and Property (A) (on the right).

We show that an $r$ satisfying properties (A) and (B) can be found for $i=1$.
The argument is the same for $i=2$ and $i=3$, and we can take the smallest
among the three resulting $r$-s.

First, consider property (A). Since the sides of $K$ are parallel to
$\ell_{1}$ and $\ell_{2}$, the portion of $K$ that lies “above” the segment
$\overline{\hat{\gamma}(t_{1})\hat{\gamma}(t_{2})}$ is in $\hat{C}$. Hence, if
we choose $r$ small enough so that $Q$ cannot intersect
$\overline{\hat{\gamma}(t_{1})\hat{\gamma}(t_{2})}$, then property (A) is
satisfied. For example, choosing $r$ to be smaller than $\frac{1}{\sqrt{2}}$
times the distance of the segments
$\overline{\hat{\gamma}(t_{1})\hat{\gamma}(t_{2})}$ and
$\overline{\hat{\gamma}(t_{1}+\varepsilon/2)\hat{\gamma}(t_{2}-\varepsilon/2)}$
works.

Using that $\gamma$ is a continuous function on a compact set, we can pick $r$
such that property (B) is satisfied. Therefore, there is an $r$ satisfying
properties (A) and (B).

The next step is a subdivision of the point set $P$ using Theorem 10, like we
did in the proof of Theorem 18. The beginning of our argument is exactly the
same.

Apply Theorem 10 for the graph given by the union of $\prec_{K_{1,2}}$,
$\prec_{K_{2,3}}$ and $\prec_{K_{3,1}}$. By Observation 16, this is indeed a
complete multidigraph on $P$.

We apply Theorem 10 with $k=3$ and $l=2$, resulting in subsets $S_{i}^{j}$ for
$i\in[3],j\in[2]$. Let $S=\bigcup\limits_{i\in[3],j\in[2]}S_{i}^{j}$. For each
point $p\in P\setminus S$ there is an $i$ such that $\prec_{K_{i,i+1}}$ has an
edge from a vertex of $S_{i,1}$ and $S_{i,2}$ to $p$. Let $P_{1},P_{2},P_{3}$
be the partition of $P\setminus S$ according to this $i$ value.

We start by coloring the points of $S$. Color the points of $S_{1,1}\cup
S_{2,1}\cup S_{3,1}$ with the first color and color the points of $S_{1,2}\cup
S_{2,2}\cup S_{3,2}$ with the second color.

Note that $m$ is at least $f(3,2)+13$. Any translate of $C$ that contains
$f(3,2)+13$ points of $P$ must contain $5$ points from either $P_{1},P_{2}$ or
$P_{3}$. (Note that the cone might contain all points of $S$). Therefore it is
enough to show that for each $i\in[3]$ the points of $P_{i}$ can be colored
with three color such that no translate of $C$ that contains at least $5$
points of $P_{i}$ is monochromatic.

Consider $P_{1}$, the proof is the same for $P_{2}$ and $P_{3}$. We divide the
translates of $C$ that intersect $Q$ into four groups. Let $\mathcal{C}_{0}$
denote the translates where $\hat{C}\cap Q=Q$. Let $\mathcal{C}_{1}$ denote
the translates for which $\partial\hat{C}\cap
Q\subset\hat{\gamma}_{[t_{1}+\varepsilon/2,t_{2}-\varepsilon/2]}$. Let
$\mathcal{C}_{2}$ denote the translates for which $\partial\hat{C}\cap
Q\cap\hat{\gamma}_{[t_{2}-\varepsilon/2,t_{3}]}\neq\emptyset$. Let
$\mathcal{C}_{3}$ denote the remaining translates for which
$\partial\hat{C}\cap
Q\cap\hat{\gamma}_{[t_{3},t_{1}+\varepsilon/2]}\neq\emptyset$.

We do not need to worry about the translates in $\mathcal{C}_{0}$, as $Q$
itself will not be monochromatic.

Take a translate $\hat{C}$ from $\mathcal{C}_{1}$ and suppose that it contains
a point $p\in P_{1}$. By Theorem 10, there is an edge of $\prec_{K_{1,2}}$
from a vertex of $S_{1,1}$ to $p$ and another edge from a vertex of $S_{1,2}$
to $p$. I.e., the cone $p+K_{1,2}$ contains a point from $S_{1,1}$ and another
point from $S_{1,2}$, and hence it is not monochromatic. From property (A) we
know that every point in $(p+K_{1,2})\cap P$ is also in $\hat{C}$. Therefore,
$\hat{C}$ is not monochromatic.

Now consider the translates in $\mathcal{C}_{2}$. From property (B) we know
that for these translates we have $\partial\hat{C}\cap
Q\subset\hat{\gamma}_{[t_{2}-\varepsilon,t_{3}+\varepsilon]}$. By the
definition of $t_{1},t_{2}$ and $t_{3}$, we know that this implies that any
two translates from $\mathcal{C}_{2}$ intersect at most once on their boundary
within $Q$, i.e., they behave as pseudohalfplanes. To turn the translates in
$\mathcal{C}_{2}$ into a pseudohalfplane arrangement as defined earlier, we
can do as follows. For a translate $\hat{C}$, replace it with the convex set
whose boundary is $\hat{\gamma}_{[t_{2}-\varepsilon,t_{3}+\varepsilon]}$
extended from its endpoints with two rays orthogonal to the segment
$\overline{\hat{\gamma}(t_{2}-\varepsilon)\hat{\gamma}(t_{3}+\varepsilon)}$.
This new family provides the same intersection pattern in $Q$ and forms a
pseudohalfplane arrangement. We can do the same with the translates in
$\mathcal{C}_{3}$. Therefore, by Corollary 8 there is a proper three-coloring
for the translates in $\mathcal{C}_{2}\cup\mathcal{C}_{3}$. ∎

##  4 Overview of the computational complexity of the algorithm

In this section we show that given a point set $P$ and a convex set $C$, we
can determine some $m=m(C)$ and calculate a three-coloring of $P$ efficiently
if $C$ is given in a natural way, for example, if $C$ is a disk. Our algorithm
is randomized and its running time is a polynomial of the number of points,
$n=|P|$.

  * •

First, we need to fix three points on the boundary,
$\tau_{1},\tau_{2},\tau_{3}\subset\partial C$ such that Lemma 15 is satisfied
with $\tau_{i}=\gamma(t_{i})$ for some $t_{i}$ and $\varepsilon>0$ for each
$i$. Note that we do not need to fix a complete parametrization $\gamma$ of
$\partial C$ or $\varepsilon>0$; instead, it is enough to choose some points
$\tau_{i}^{\scalebox{0.6}{$--$}}$ and $\tau_{i}^{\scalebox{0.6}{$++$}}$ that
satisfy the conclusion of Lemma 15 if we assume
$\tau_{i}^{\scalebox{0.6}{$--$}}=\gamma(t_{i}-\varepsilon)$ and
$\tau_{i}^{\scalebox{0.6}{$++$}}=\gamma(t_{i}+\varepsilon)$ for each $i$. If
$C$ has a smooth boundary, like a disk, we can pick
$\tau_{1},\tau_{2},\tau_{3}$ to be the touching points of an equilateral
triangle with $C$ inscribed in it. If the boundary of $C$ contains vertex-type
sharp turns, the complexity of finding these turns depends on how $C$ is
given, but for any reasonable input method, this should be straight-forward.
After that, one can follow closely the steps of the proof of the Illumination
conjecture in the plane to get an algorithm, but apparently, this has not yet
been studied in detail.

  * •

To pick $r$, the side length of the squares of the grid, we can fix some
arbitrary points $\tau_{i}^{\scalebox{0.6}{$-$}}$ between
$\tau_{i}^{\scalebox{0.6}{$--$}}$ and $\tau_{i}$, and points
$\tau_{i}^{\scalebox{0.6}{$+$}}$ between $\tau_{i}$ and
$\tau_{i}^{\scalebox{0.6}{$++$}}$, to play the roles of
$\gamma(t_{i}-\varepsilon/2)$ and $\gamma(t_{i}+\varepsilon/2)$, respectively,
for each $i$. It is sufficient to pick $r$ so that $r\sqrt{2}$, the diameter
of the square of side length $r$, is less than

    * –

the distance of $\tau_{i}^{\scalebox{0.6}{$+$}}$ and
$\tau_{i+1}^{\scalebox{0.6}{$-$}}$ from the segment
$\overline{\tau_{i}\tau_{i+1}}$,

    * –

the distance of $\tau_{i}^{\scalebox{0.6}{$-$}}$ from
$\tau_{i}^{\scalebox{0.6}{$--$}}$, and

    * –

the distance of $\tau_{i}^{\scalebox{0.6}{$+$}}$ from
$\tau_{i}^{\scalebox{0.6}{$++$}}$,

for each $i$, to guarantee that properties (A) and (B) are satisfied.

  * •

Set $m=f(3,2)+13$, which is an absolute constant given by Theorem 10. We need
to construct the complete multidigraph given by the tri-partition cones
determined by $\tau_{1},\tau_{2},\tau_{3}$, which needs a comparison for each
pair of points. To obtain the subsets $S_{i}^{j}\subset P$ for
$i\in[3],j\in[2]$, where $P$ is the set of points that are contained in a
square of side length $r$, we randomly sample the required number of points
from each of the constantly many $T_{j_{1},\dots,j_{i}}$ according to the
probability distributions $w_{j_{1},\dots,j_{i}}$ given by Lemma 22. These
probability distributions can be computed by LP. With high probability, all
the $S_{i}^{j}$-s will be disjoint—otherwise, we can resample until we obtain
disjoint sets.

  * •

To find the three-coloring for the two pseudohalfplane arrangements, given by
Corollary 8, it is enough to determine the two-coloring given by Theorem 7 for
one pseudohalfplane arrangement. While not mentioned explicitly in [20], the
polychromatic $k$-coloring can be found in polynomial time if we know the
hypergraph determined by the range space, as this hypergraph can only have a
polynomial number of edges, and the coloring algorithm only needs to check
some simple relations among a constant number of vertices and edges.

  * •

Finally, to compute a suitable $m^{\prime}$ for Theorem 1 from the $m$ of
Theorem 20, it is enough to know any upper bound $B$ for the diameter of $C$,
and let $m^{\prime}=m(B/r+2)^{2}$.

##  5 Open questions

It is a natural question whether there is a universal $m$ that works for all
convex bodies in Theorem 1, like in Theorem 20. This would follow if we could
choose $r$ to be a universal constant. While the $r$ given by our algorithm
can depend on $C$, we can apply an appropriate affine transformation to $C$
before choosing $r$; this does not change the hypergraphs that can be realized
with the range space determined by the translates of $C$. To ensure that
properties (A) and (B) are satisfied would require further study of the
Illumination conjecture.

Our bound for $m$ is quite large, even for the unit disk, both in Theorems 1
and 20, which is mainly due to the fact that $f(3,2)$ given by Theorem 10 is
huge. It has been conjectured that in Theorem 9 the optimal value is $f(3)=3$,
and a similarly small number seems realistic for $f(3,2)$ as well.

While Theorem 1 closed the last question left open for primal hypergraphs
realizable by translates of planar bodies, the respective problem is still
open in higher dimensions. While it is not hard to show that some hypergraphs
with high chromatic number often used in constructions can be easily realized
by unit balls in $\mathbb{R}^{5}$, we do not know whether the chromatic number
is bounded or not in $\mathbb{R}^{3}$. From our Union Lemma (Lemma 6) it
follows that to establish boundedness, it would be enough to find a
polychromatic $k$-coloring for pseudohalfspaces, whatever this word means.

## References

  * [1] Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi.  Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs.  Acta Math. Univ. Comenian. (N.S.), 88(3):363–370, 2019.
  * [2] Eyal Ackerman, Balázs Keszegh, and Máté Vizer.  Coloring points with respect to squares.  Discrete & Computational Geometry, 58(4):757–784, 2017.
  * [3] Noga Alon, Graham Brightwell, H. A. Kierstead, A. V. Kostochka, and Peter Winkler.  Dominating sets in $k$-majority tournaments.  J. Combin. Theory Ser. B, 96(3):374–387, 2006.
  * [4] Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman, David Orden, Pedro Ramos.  Decomposition of multiple coverings into more parts.  Discrete & Computational Geometry, 44(3):706–723, 2010.
  * [5] Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Michael Hoffmann, Kolja Knauer, Stefan Langerman, Michał Lasoń, Piotr Micek, Günter Rote, and Torsten Ueckerdt.  Coloring hypergraphs induced by dynamic point sets and bottomless rectangles.  In Algorithms and data structures, volume 8037 of Lecture Notes in Comput. Sci., 73–84. Springer, Heidelberg, 2013.
  * [6] Károly Bezdek and Muhammad A. Khan.  The geometry of homothetic covering and illumination.  In Discrete geometry and symmetry, volume 234 of Springer Proc. Math. Stat., pages 1–30. Springer, Cham, 2018.
  * [7] Nicolas Bousquet, William Lochet, and Stéphan Thomassé.  A proof of the Erdos-Sands-Sauer-Woodrow conjecture.  J. Combin. Theory Ser. B, 137:316–319, 2019.
  * [8] Jean Cardinal, Kolja Knauer, Piotr Micek, Dömötör Pálvölgyi, Torsten Ueckerdt, Narmada Varadarajan.  Colouring bottomless rectangles and arborescences.  Proceedings of EuroCG 2020, paper 47.
  * [9] Jean Cardinal, Kolja Knauer, Piotr Micek, and Torsten Ueckerdt.  Making triangles colorful.  J. Comput. Geom., 4(1):240–246, 2013.
  * [10] Jean Cardinal, Kolja Knauer, Piotr Micek, and Torsten Ueckerdt.  Making octants colorful and related covering decomposition problems.  SIAM J. Discrete Math., 4(28):1948–1959, 2014.
  * [11] Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos.  Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.  Random Struct. Algorithms, 34:11–23, 2009.
  * [12] Gábor Damásdi and Dömötör Pálvölgyi.  Realizing an m-uniform four-chromatic hypergraph with disks.  Combinatorica, to appear.
  * [13] Gábor Damásdi and Dömötör Pálvölgyi.  Unit disks hypergraphs are three-colorable.  Extended Abstracts EuroComb 2021. Trends in Mathematics, vol 14, 483–489, 2021.
  * [14] David C. Fisher and Jennifer Ryan.  Probabilities within optimal strategies for tournament games.  Discrete Applied Math., 56, (1995), 87–91
  * [15] Matt Gibson and Kasturi Varadarajan.  Optimally decomposing coverings with translates of a convex polygon.  Discrete Comput. Geom., 46(2):313–333, 2011.
  * [16] Balázs Keszegh.  Coloring half-planes and bottomless rectangles.  Computational geometry, 45(9):495–507, 2012.
  * [17] Balázs Keszegh and Dömötör Pálvölgyi.  Octants are cover decomposable.  Discrete Comput. Geom., 47:598–609, 2012.
  * [18] Balázs Keszegh and Dömötör Pálvölgyi.  Convex polygons are self-coverable.  Discrete Comput. Geom., 51(4):885–895, 2014.
  * [19] Balázs Keszegh and Dömötör Pálvölgyi.  Proper coloring of geometric hypergraphs.  Discrete Comput. Geom., 62(3):674–689, 2019.
  * [20] Balázs Keszegh and Dömötör Pálvölgyi.  An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes.  J. Comput. Geom., 10(1):1–26, 2019.
  * [21] István Kovács.  Indecomposable coverings with homothetic polygons.  Discrete & Computational Geometry, 53(4):817–824, 2015.
  * [22] Friedrich W. Levi.  Überdeckung eines Eibereiches durch Parallelverschiebung seines offenen Kerns.  Arch. Math. (Basel), 6:369–370, 1955.
  * [23] János Pach.  Decomposition of multiple packing and covering.  Diskrete Geometrie, 2. Kolloq. Math. Inst. Univ. Salzburg, 169–178, 1980.
  * [24] János Pach.  Covering the plane with convex polygons.  Discrete Comput. Geom., 1(1):73–81, 1986.
  * [25] János Pach and Dömötör Pálvölgyi.  Unsplittable coverings in the plane.  Advances in Mathematics, 302:433–457, 2016.
  * [26] János Pach, Dömötör Pálvölgyi, Géza Tóth.  Survey on decomposition of multiple coverings.  In Geometry–Intuitive, Discrete, and Convex, 219–257. Springer, 2013.
  * [27] János Pach, Gábor Tardos, and Géza Tóth.  Indecomposable coverings.  In Discrete geometry, combinatorics and graph theory, volume 4381 of Lecture Notes in Comput. Sci., 135–148. Springer, Berlin, 2007.
  * [28] János Pach and Gábor Tardos.  Coloring axis-parallel rectangles.  In J. of Combinatorial Theory, Series A, 117(6):776–782, 2010.
  * [29] Dömötör Pálvölgyi.  Indecomposable coverings with concave polygons.  Discrete Comput. Geom., 44(3):577–588, 2010.
  * [30] Dömötör Pálvölgyi and Géza Tóth.  Convex polygons are cover-decomposable.  Discrete & Computational Geometry, 43(3):483–496, 2010.
  * [31] Ioannis Papadoperakis.  An estimate for the problem of illumination of the boundary of a convex body in $E^{3}$.  Geom. Dedicata, 75(3):275–285, 1999.
  * [32] Bill Sands, Norbert Sauer, and Robert Woodrow.  On monochromatic paths in edge-coloured digraphs.  J. Combin. Theory Ser. B, 33(3):271–275, 1982.
  * [33] Shakhar Smorodinsky and Yelena Yuditsky.  Polychromatic coloring for half-planes.  J. Combin. Theory Ser. A, 119(1):146–154, 2012.
  * [34] Gábor Tardos and Géza Tóth.  Multiple coverings of the plane with triangles.  Discrete & Computational Geometry, 38:443–450, 2007.

##  Appendix A Proof of Theorem 10

Here we give the full proof of Theorem 10. Most of our arguments follow very
closely the proof of Theorem 9 from [7].

Theorem 10. For every pair of positive integers $k$ and $l$, there exist an
integer $f(k,l)$ such that if $D=(V,A)$ is a complete multidigraph whose arcs
are the union of $k$ quasi orders $\prec_{1},\dots,\prec_{k}$, then $V$
contains a family of pairwise disjoint subsets $S_{i}^{j}$ for $i\in[k]$,
$j\in[l]$ with the following properties:

  * •

$|\bigcup\limits_{i,j}S_{i}^{j}|\leq f(k,l)$

  * •

For each vertex $v\in V\setminus\bigcup\limits_{i,j}S_{i}^{j}$ there is an
$i\in[k]$ such that for each $j\in[l]$ there is an edge of $\prec_{i}$ from a
vertex of $S_{i}^{j}$ to $v$.

Let us quickly recap the main steps from the proof of Theorem 9 from [7]. For
a function $w:V\rightarrow\mathbb{R}$ and $S\subset V$ let
$w(S)=\sum\limits_{x\in S}f(x)$. We say that $w:V\rightarrow[0,1]$ is a
_probability distribution_ on $V$ if $w(V)=1$. First they carefully define a
partition of the vertex set. Then for each part $P$ of the partition a
probability distribution $w_{P}$ is defined which is concentrated on $P$. Each
part of the partition is dominated independently of the other parts using a
probabilistic argument. Namely, they show that we can pick some points
according to $w_{P}$ and these points will dominate $P$ with positive
probability. Also, each part is dominated using edges of just one $\prec_{i}$.
The main reason that the proof does not immediately work for Theorem 10 is
that the dominating sets for the different parts might intersect.

Our proof of Theorem 10 follows a very similar path. We will also define a
partition of the vertex set (see Figure 5) and corresponding probability
distributions. Then we will apply the probabilistic argument for the parts
simultaneously to ensure that the dominating sets of the parts are disjoint.
We will apply the probabilistic argument $l$ times for each part. To be able
to ensure disjointness of the $S_{i}^{j}$-s, the partition and the
distributions are created a bit more carefully; we ensure that a vertex cannot
have too much weight in any of the probability distributions. This way the
probability of picking any vertex in two different $S_{i}^{j}$-s will be
sufficiently small.

We start with a number of useful lemmas. The following variant of LP duality
was stated in this context in [3, Lemma 5].

######  Lemma 21 (Alon et al. [3]).

If $D=(V,A)$ is a complete multidigraph, then there exists a probability
distribution $w$ on $V$ such that $w(N^{-}(x))\geq 1/2$ for each $x\in V$.

We prove the following modification of Lemma 21 to obtain a $w$ whose min-
entropy is large.

######  Lemma 22.

Let $D=(V,A)$ be a complete multidigraph and let $0<\delta<1$ be a fixed
number. If $|V|>\frac{1}{\delta}$, then there exists a probability
distribution $w$ on $V$ such that for each $x\in V$ one of the following
holds:

  * •

$w(x)\leq 2\delta$ and $w(N^{-}(x))\geq 1/2$

  * •

$\delta\leq w(x)\leq 4\delta$

Note that the second condition holds for at most $1/\delta$ vertices.

###### Proof.

We define a sequence of probability distributions $w_{1},\dots,w_{\lfloor
1/\delta\rfloor}$ and a sequence of subsets of $V$ called
$R_{1},\dots,R_{\lfloor 1/\delta\rfloor}$. Let $w_{1}$ be a probability
distribution given by Lemma 21, that is $w_{1}(N^{-}(x))\geq 1/2$ for all
$x\in V$. Let $R_{1}=\emptyset$ if $w_{1}(x)<1$ for every $x\in V$ and let
$R_{1}=\\{x\\}$ if $w_{1}$ is concentrated on a single vertex $x\in V$.

For $i>1$ we obtain $w_{i}$ by applying Lemma 21 for the induced complete
multidigraph $D[V\setminus R_{i-1}]$. That is, $w_{i}$ is a probability
distribution such that $w_{i}(N^{-}(x))\geq 1/2$ for all $x\in V\setminus
R_{i-1}$ and $w_{i}(x)=0$ for $x\in R_{i-1}$. Let $R_{i}=\\{x\in
V|\sum\limits_{j=1}^{i}w_{j}(x)\geq 1\\}$.

To use Lemma 21, we need to check that $V\setminus R_{i-1}$ is nonempty. If
$V\setminus R_{i-1}$ is empty, then by the definition of $R_{i-1}$ we have
$\sum\limits_{j=1}^{i-1}w_{j}(x)\geq 1$ for each $x\in V$. Hence
$i-1=\sum\limits_{j=1}^{i-1}w_{j}(V)=\sum\limits_{x\in
V}\sum\limits_{j=1}^{i-1}w_{j}(x)\geq|V|\cdot 1$. Since
$i-1<\frac{1}{\delta}$, this contradicts the $|V|>\frac{1}{\delta}$ assumption
of the lemma.

Let $w=\frac{1}{\lfloor 1/\delta\rfloor}\sum\limits_{i=1}^{\lfloor
1/\delta\rfloor}w_{i}$. Clearly, this is a probability distribution on $V$. We
have to check the correctness of $w$. The first condition holds for vertices
not in $R_{\lfloor 1/\delta\rfloor}$ and the second one for the vertices of
$R_{\lfloor 1/\delta\rfloor}$.

If $x\in V\setminus R_{\lfloor 1/\delta\rfloor}$, then

$w(N^{-}(x))=\frac{1}{\lfloor 1/\delta\rfloor}\sum\limits_{i=1}^{\lfloor
1/\delta\rfloor}w_{i}(N^{-}(x))\geq\frac{1}{\lfloor 1/\delta\rfloor}\lfloor
1/\delta\rfloor\frac{1}{2}=\frac{1}{2}.$

Since $x\notin R_{\lfloor 1/\delta\rfloor}$ and $0<\delta<1$, we have
$w(x)\leq\frac{1}{\lfloor 1/\delta\rfloor}\cdot 1\leq 2\delta$.

In the other case, when $x\in R_{\lfloor 1/\delta\rfloor}$, then by definition
$w(x)\geq\frac{1}{\lfloor 1/\delta\rfloor}\sum\limits_{i=1}^{\lfloor
1/\delta\rfloor}w_{i}(x)\geq\frac{1}{\lfloor 1/\delta\rfloor}\geq\delta$. On
the other hand, if $j$ is the smallest number for which $x\in R_{j}$, then
$\sum\limits_{i=1}^{j-1}w_{i}(x)\leq 1$ and $w_{k}(x)=0$ for $k>j$. Therefore,

$w(x)=\frac{1}{\lfloor 1/\delta\rfloor}\sum\limits_{i=1}^{\lfloor
1/\delta\rfloor}w_{i}(x)=\frac{1}{\lfloor
1/\delta\rfloor}\sum\limits_{i=1}^{j-1}w_{i}(x)+\frac{1}{\lfloor
1/\delta\rfloor}w_{j}(x)\leq 2\delta+2\delta=4\delta.$

∎

An easy consequence of Lemma 22 is the following.

######  Lemma 23.

Let $0<\delta<1$ be fixed and let $D=(V,A)$ be a complete multidigraph on at
least $1/\delta$ vertices whose arc set is the union of $k$ quasi orders. Then
there exists a probability distribution $w$ on $V$ and a partition of $V$ into
sets $T_{1},T_{2},\dots,T_{k},R$ such that for every $i\in[k]$ and $x\in
T_{i}$, we have $w(x)\leq 2\delta$ and $w(N^{-}_{i}(x))\geq 1/2k$ and for
every $x\in R$ we have $\delta\leq w(x)\leq 4\delta$.

###### Proof.

Take $w$ according to Lemma 22. For every $i\in[k]$, let
$T_{i}^{\prime}=\\{x\in V|w(N^{-}_{i}(x))\geq 1/2k\\}$ and let $R$ be the rest
of the vertices. As $\sum_{i=1}^{k}w(N^{-}_{i}(x))\geq w(N^{-}(x)$, the sets
$T_{i}^{\prime}$ cover those vertices that satisfy the first property in Lemma
22. By making the $T_{i}$-s disjoint, we can obtain a partition with the
required properties. ∎

###### Proof of Theorem 10.

Fix $0<\delta<1$, we will choose its value later. Let $\mathcal{I}$ denote the
set of sequences of length at most $k+1$ whose terms are from $[k]$, including
the empty set. In other words
$\mathcal{I}=\\{\emptyset\\}\cup\bigcup\limits_{l=1}^{k+1}[k]^{l}$.

For a complete multidigraph $D=(V,A)$ we are going to define two systems of
subsets $\\{T_{j_{1},\dots,j_{i}}\\}_{(j_{1},\dots,j_{i})\in Ind_{1}}$ and
$\\{R_{j_{1},\dots,j_{i}}\\}_{(j_{1},\dots,j_{i})\in Ind_{2}}$ of the vertex
set for some index sets $Ind_{1},Ind_{2}\subset\mathcal{I}$. The process that
defines these subsets is similar to a tree traversal algorithm. The root node
corresponds to $V$ and the children of a given node in the tree will
correspond to a partition of the node. Therefore in the end the leaves of the
tree provide a partition of the vertex set. For each $T_{j_{1},\dots,j_{i}}$
we also define a probability distribution $w_{j_{1},\dots,j_{i}}$ which is
concentrated on $T_{j_{1},\dots,j_{i}}$.

$R_{\emptyset}$$T_{2}$$T_{1,1}$$T_{1,2}$$R_{2}$$T_{2,3}$$T_{2,2}$$T_{2,1}$$T_{1,3}$$T_{3}$$R_{1}$$T_{1}$$R_{1,2,3}$$T_{1,2,3,1}$$T_{1,2,3,2}$$T_{1,2,3,3}$$R_{1,2}$$T_{1,2,1}$$T_{1,2,2}$$T_{1,2,3}$$T_{\emptyset}$$R_{2,3}$$T_{2,3,1}$$T_{2,3,2}$$T_{2,3,3}$$R_{2,1}$$T_{2,1,1}$$T_{2,1,2}$$T_{2,1,3}$$R_{2,3,1}$$T_{2,1,3,1}$$T_{2,1,3,2}$$T_{2,1,3,3}$$R_{2,1,3}$$T_{2,1,3,1}$$T_{2,1,3,2}$$T_{2,1,3,3}$

Figure 5: The outcome of the partition process for $k=3$ assuming that the
size of $T_{3}$ and $T_{1,3}$ is less than $1/\delta$.

We start by setting $T_{\emptyset}=V$ and we apply Lemma 23 for
$T_{\emptyset}$ and our fixed $\delta$ to obtain $T_{1},T_{2},\dots,T_{k}$ and
$R_{\emptyset}$ together with a probability distribution $w_{\emptyset}$.

Then, as long as possible, we do the following step. We pick a previously not
selected $T_{j_{1},\dots,j_{i}}$ from the already defined ones such that
$j_{1},\dots,j_{i}$ are pairwise distinct, and
$|T_{j_{1},\dots,j_{i}}|>\frac{1}{\delta}$. For such a $T_{j_{1},\dots,j_{i}}$
we apply Lemma 23 to obtain the partition
$T_{j_{1},\dots,j_{i},1},\dots,T_{j_{1},\dots,j_{i},k},R_{j_{1},\dots,j_{i}}$
and a probability distribution $w_{j_{1},\dots,j_{i}}$. This process
terminates in (strictly) less than $|\mathcal{I}|\leq k^{k+2}$ steps as no
index sequence can be longer than $k+1$. Let $Ind_{1}$ and $Ind_{2}$ denote
the index sets for the $T_{j_{1},\dots,j_{i}}$-s and
$R_{j_{1},\dots,j_{i}}$-s. From Lemma 23 we know the following:

  * •

$|R_{j_{1},\dots,j_{i}}|\leq\frac{1}{\delta}$ for each $(j_{1},\dots,j_{i})\in
Ind_{2}$.

  * •

For every $r\in[k]$ and $x\in T_{j_{1},\dots,j_{i},r}$ we have
$w_{j_{1},\dots,j_{i}}(N^{-}_{r}(x))\geq 1/2k$.

  * •

$w_{j_{1},\dots,j_{i}}(x)\leq 4\delta$ for every $x\in V$ and every
$(j_{1},\dots,j_{i})\in Ind_{2}$.

When the process halts, we define a partition of $V$ by taking every set
corresponding to a leaf, i.e., every set of the following three kinds:

  1. 1.

$R_{j_{1},\dots,j_{i}}$-s

  2. 2.

$T_{j_{1},\dots,j_{i}}$-s that have fewer elements than $\frac{1}{\delta}$

  3. 3.

$T_{j_{1},\dots,j_{i}}$-s where $j_{i}=j_{r}$ for some $r<i$

These sets are clearly disjoint, and they cover the vertex set, since the
process halted. Let $R$ denote the union of the $R_{j_{1},\dots,j_{i}}$-s, let
$T_{small}$ denote the union the $T_{j_{1},\dots,j_{i}}$-s that have fewer
elements than $1/\delta$ and finally let $T_{rep}$ denote the union of the
$T_{j_{1},\dots,j_{i}}$-s where $j_{i}=j_{r}$ for some $r<i$.

We dominate each part of the partition. Since each $R_{j_{1},\dots,j_{i}}$ has
fewer than $\frac{1}{\delta}$ elements, we have
$|R|\leq\frac{1}{\delta}|Ind_{2}|\leq\frac{1}{\delta}k^{k+2}$. Similarly
$|T_{small}|\leq\frac{1}{\delta}k^{k+2}$. We will simply put the vertices of
$R\cup T_{small}$ into $S_{1}^{1}$ but we will not use them to dominate any
point. Later, when we pick $\delta$, we will see that
$\frac{2}{\delta}k^{k+2}$ is upper bounded by a function of $k$ and $l$, so we
have not added too many vertices here.

It remains to dominate the vertices in $T_{rep}$. Let $I_{rep}\subset Ind_{1}$
be the index set of those $T_{j_{1},\dots,j_{i}}$-s where $j_{i}=j_{r}$ for
some $r<i$.

Let us fix $(j_{1},\dots,j_{i})\in I_{rep}$ and $o\in[l]$. First we explain
how to chose a set $V_{j_{1},\dots,j_{i}}^{o}\subset V$ such that
$V_{j_{1},\dots,j_{i}}^{o}$ dominates $T_{j_{1},\dots,j_{i}}$ and then we will
argue that this can be done simultaneously for every $(j_{1},\dots,j_{i})\in
I_{rep}$ and $o\in[l]$ in such a way that the $V_{j_{1},\dots,j_{i}}^{o}$-s
are disjoint.

For a fixed $(j_{1},\dots,j_{i})\in I_{rep}$, consider
$T_{j_{1},\dots,j_{i}}\subset T_{j_{1},\dots,j_{i-1}}\subset
T_{j_{1},\dots,j_{r-1}}$ such that $j_{i}=j_{r}$. The idea is that if we
appropriately pick $V_{j_{1},\dots,j_{i}}^{o}\subset T_{j_{1},\dots,j_{r-1}}$,
such that $V_{j_{1},\dots,j_{i}}^{o}$ dominates a large fraction of
$T_{j_{1},\dots,j_{i-1}}$ through the edges of $\prec_{j_{r}}$, then that
large fraction dominates entirely $T_{j_{1},\dots,j_{i}}$, and since
$j_{r}=j_{i}$, this happens through the edges of $\prec_{j_{i}}$ again. By
transitivity, this implies that $T_{j_{1},\dots,j_{i}}$ is dominated by
$V_{j_{1},\dots,j_{i}}^{o}$. To put this idea into precise terms note that for
each $x\in T_{j_{1},\dots,j_{i}}$ we have
$w_{j_{1},\dots,j_{i-1}}(N_{j_{i}}^{-}(x))\geq\frac{1}{2k}$. Hence, if
$w_{j_{1},\dots,j_{i-1}}(N^{+}_{j_{i}}(V_{j_{1},\dots,j_{i}}^{o}))>1-\frac{1}{2k}$,
then $T_{j_{1},\dots,j_{i}}$ is dominated by $V_{j_{1},\dots,j_{i}}^{o}$.

Let $0<\varepsilon<1$ be fixed, we will choose its value later. Let
$g(\varepsilon)=\lfloor\frac{\ln(\varepsilon)}{\ln(1-\frac{1}{2k})}\rfloor+1$
and let $V_{j_{1},\dots,j_{i}}^{o}$ be a multiset of $g(\varepsilon)$ elements
picked independently at random from $T_{j_{1},\dots,j_{r-1}}$ according to the
distribution $w_{j_{1},\dots,j_{r-1}}$. For every vertex $x\in
T_{j_{1},\dots,j_{i-1}}$, $\mathbb{P}(x\in
N_{j_{i}}^{+}(V_{j_{1},\dots,j_{i}}^{o}))\geq
1-(1-\frac{1}{2k})^{g(\varepsilon)}\geq 1-\varepsilon$. Therefore, by
linearity of expectation,

$\mathbb{E}(w_{j_{1},\dots,j_{i-1}}(N^{+}_{j_{i}}(V_{j_{1},\dots,j_{i}}^{o})))\geq\sum_{x\in
T_{j_{1},\dots,j_{i-1}}}w_{j_{1},\dots,j_{i-1}}(x)\cdot(1-\varepsilon)\geq
1-\varepsilon.$

This already shows that if $\varepsilon\leq 1/2k$, there is a positive
probability that $V_{j_{1},\dots,j_{i}}^{o}$ dominates
$T_{j_{1},\dots,j_{i}}$. But we will need a smaller $\varepsilon$ for
disjointness.

Let $X$ be the random variable $\sum\limits_{(j_{1},\dots,j_{i})\in
I_{rep},o\in[l]}w_{j_{1},\dots,j_{i-1}}(N^{+}_{j_{i}}(V_{j_{1},\dots,j_{i}}^{o}))$.
By our reasoning above, $\mathbb{E}(X)\geq l|I_{rep}|(1-\varepsilon).$

Let $Y$ be the indicator variable of the event that the sets
$V_{j_{1},\dots,j_{i}}^{o}$ for $(j_{1},\dots,j_{i})\in I_{rep},o\in[l]$ are
pairwise disjoint. Let us consider the random variable $X\cdot Y$. Suppose
that $\mathbb{P}(X\cdot Y>l|I_{rep}|-\frac{1}{2k})>0$. This would imply that
$Y=1$, i.e., the $V_{j_{1},\dots,j_{i}}^{o}$-s are pairwise disjoint. Since
$w_{j_{1},\dots,j_{i-1}}(N^{+}_{j_{i}}(V_{j_{1},\dots,j_{i}}^{o}))\leq 1$ for
each $(j_{1},\dots,j_{i})\in I_{rep}$, it would also imply that
$w_{j_{1},\dots,j_{i-1}}(N^{+}_{j_{i}}(V_{j_{1},\dots,j_{i}}^{o}))>1-\frac{1}{2k}$
for each $(j_{1},\dots,j_{i})\in I_{rep}$ and $o\in[l]$. From here it will be
easy to construct the required sets $S_{i}^{j}$.

We will show an lower bound on $\mathbb{E}(X\cdot Y)$. Since $Y$ is an
indicator variable, we have

$\mathbb{E}(X\cdot Y)\geq\mathbb{E}(X)-\max(X)\cdot\mathbb{P}(Y=0).$

Clearly $\max(X)\leq l|I_{rep}|$. To bound $\mathbb{P}(Y=0)$, note that in
total we have picked at most $N=l|I_{rep}|g(\epsilon)\leq lk^{k+2}g(\epsilon)$
elements. Every time we picked an element, the probability distribution was
smaller than $4\delta$ on each element of $V$. Hence

$\mathbb{P}(Y=0)\leq\binom{N}{2}4\delta\leq N^{2}2\delta$

Therefore,

$\mathbb{E}(X\cdot Y)\geq\mathbb{E}(X)-\max(X)\cdot\mathbb{P}(Y=0)\geq$

$\geq
l|I_{rep}|(1-\varepsilon)-l|I_{rep}|N^{2}2\delta=l|I_{rep}|(1-\varepsilon-N^{2}2\delta)$

Pick $\varepsilon=\frac{1}{4lk^{k+3}}$ and
$\delta=\frac{1}{8l^{3}k^{3k+7}g(\varepsilon)^{2}}$. With this choice
$N^{2}2\delta\leq\frac{2l^{2}k^{2k+4}g(\varepsilon)^{2}}{8l^{3}k^{3k+7}g(\varepsilon)^{2}}=\frac{1}{4lk^{k+3}}$.

Therefore,

$\mathbb{E}(X\cdot Y)\geq l|I_{rep}|(1-\varepsilon-N^{2}2\delta)\geq
l|I_{rep}|(1-\frac{1}{4lk^{k+3}}-\frac{1}{4lk^{k+3}})$

$\geq l|I_{rep}|(1-\frac{1}{2kl|I_{rep}|})=l|I_{rep}|-\frac{1}{2k}.$

Hence, it is possible that $X\cdot Y\geq l|I_{rep}|-\frac{1}{2k}$. In this
case the $V_{j_{1},\dots,j_{i}}^{o}$-s are pairwise disjoint and each
$T_{j_{1},\dots,j_{i}}$ is dominated by $V_{j_{1},\dots,j_{i}}^{o}$ through
the edges of $\prec_{j_{i}}$.

Finally, let $S_{i}^{j}=\bigcup\limits_{({j_{1},\dots,j_{r},i})\in
I_{rep}}V_{j_{1},\dots,j_{r},i}^{j}$ (be careful that $i$ denotes something
else than in the paragraph above). The $S_{i}^{j}$-s are also pairwise
disjoint. For any vertex $v\in V\setminus\bigcup\limits_{i,j}S_{i}^{j}\subset
T_{rep}$ there is a $T_{j_{1},\dots,j_{r},i}$ containing it for some
$({j_{1},\dots,j_{r},i})\in I_{rep}$ (recall that we added $R\cup T_{small}$
to $S_{1}^{1}$), hence there is an edge of $\prec_{i}$ from $v$ to a vertex of
$S^{j}_{i}$ for each $j\in[l]$.

To wrap up the proof, we calculate the size of
$\bigcup\limits_{i,j}S_{i}^{j}$. We placed $R\cup T_{small}$ into $S_{1}^{1}$
and we have at most $g(\varepsilon)$ elements in each
$V_{j_{1},\dots,j_{i}}^{o}$. Therefore, we have at most

$\frac{2}{\delta}k^{k+2}+lk^{k+2}g(\varepsilon)\leq
2\cdot{8l^{3}k^{3k+7}(\lfloor\frac{\ln(\frac{1}{4lk^{k+3}})}{\ln(1-\frac{1}{2k})}\rfloor+1)^{2}}k^{k+2}+lk^{k+2}(\lfloor\frac{\ln(\frac{1}{4lk^{k+3}})}{\ln(1-\frac{1}{2k})}\rfloor+1)$

elements in $\bigcup\limits_{i,j}S_{i}^{j}$. ∎

##  Appendix B Sketch of generalization of Theorem 5

Here we give a sketch of the construction that proves the following
generalization of Theorem 5.

######  Theorem 24.

Let $C$ be any convex body in the plane that boundary has a neighborhood where
it is smooth. For any positive integer $m$, there exists a 3-chromatic
$m$-uniform hypergraph that is realizable with translates of $C$.

First we describe the abstract 3-chromatic $m$-uniform hypergraph, first used
in [29], that we realize with the translates of $C$; we briefly recall its
definition from [25].

For any positive integers $k$ and $l$ the abstract hypergraph
${\mathcal{H}}(k,l)$ with vertex set $V(k,l)$ and edge set $E(k,l)$ is defined
recursively. The edge set $E(k,l)$ is the disjoint union of two sets,
$E(k,l)=E_{R}(k,l)\cup E_{B}(k,l)$, where the subscripts $R$ and $B$ stand for
red and blue. All edges belonging to $E_{R}(k,l)$ are of size $k$, all edges
belonging to $E_{B}(k,l)$ are of size $l$. In other words,
${\mathcal{H}}(k,l)$ is the union of a $k$-uniform and an $l$-uniform
hypergraph. If $k=l=m$, we get an $m$-uniform hypergraph.

######  Definition 25.

Let $k$ and $l$ be positive integers.

  1. 1.

For $k=1$, let $V(1,l)$ be an $l$-element set.
Set $E_{R}(1,l):=V(1,l)$ and $E_{B}(1,l):=\\{V(1,l)\\}$.

  2. 2.

For $l=1$, let $V(k,1)$ be a $k$-element set.
Set $E_{R}(k,1):=\\{V(k,1)\\}$ and $E_{B}(k,1):=V(k,1)$.

  3. 3.

For any $k,l>1$, we pick a new vertex $p$, called the root, and let

$V(k,l):=V(k-1,l)\cup V(k,l-1)\cup\\{p\\},$
$E_{R}(k,l):=\\{e\cup\\{p\\}\,:\,e\in E_{R}(k-1,l)\\}\cup E_{R}(k,l-1),$
$E_{B}(k,l):=E_{B}(k-1,l)\cup\\{e\cup\\{p\\}\,:\,e\in E_{B}(k,l-1)\\}.$

$p$ $(root)$$P(k,l-1)$$P(k-1,l)$

Figure 6: The recursive step 3. of the construction with unit halfdisks.

It was shown in [29] that for any positive integers $k,l$, the hypergraph
${\mathcal{H}}(k,l)$ is not $2$-colorable. Moreover, for every coloring of
$V(k,l)$ with red and blue, there is an edge in $E_{R}(k,l)$ such that all of
its $k$ vertices are red or an edge in $E_{B}(k,l)$ such that all of its $l$
vertices are blue.

To prove Theorem 24, it is sufficient to show that 1-3. in Definition 25 can
be realized with the translates of $C$. Our realization will be such that all
the translates of $C$ realizing edges from $E_{R}(k,l)$ are very close to each
other, and similarly, all the translates realizing edges from $E_{B}(k,l)$ are
also very close to each other. Moreover, a translate realizing an edge from
$E_{R}(k,l)$ is always intersected, or almost intersected, by a translate
realizing an edge from $E_{B}(k,l)$ very close to the smooth neighborhood on
the boundary of $C$.

For 1. and 2., such a realization is trivial to be found. For 3., the
recursive step, it is depicted for the unit halfdisk in Figure 6 how the two
points sets $P(k-1,l)$ and $P(k,l-1)$, representing the vertices $V(k-1,l)$
and $V(k,l-1)$, can be put together to form the point set $P(k,l)$ with the
addition of a new point, $p$ (the root), representing the vertices of
$V(k,l)$. For other $C$ a similar construction works, but we do not go into
details about how the precise direction of translation needs to be chosen,
close to the supporting line of the smooth neighborhood guaranteed by the
condition of Theorem 24. This finishes the description of the construction.