EuroCG 2015, Ljubljana, Slovenia, March 16–18, 2015

Kinetic Conflict-Free Coloring∗Mark de Berg†

Tim Leijssen†

Abstract
A conflict-free coloring, or CF-coloring for short, of a
set P of points in the plane with respect to disks is acoloring of the points of P with the following property:
for any disk D containing at least one point of P there
is a point p ∈ P ∩ D so that no other point q ∈ P ∩ D
has the same color as p. In this paper we study the
problem of maintaining such a CF-coloring when the
points in P move. We present two methods for thisand evaluate the maximum number of colors used aswell as the number of recolorings, both in theory andexperimentally.
1

Introduction

Wireless communication is commonplace in many applications, varying from mobile consumer devices likecell-phones to specialized networks for autonomous
robots. For clear wireless communication it is important to avoid interference. In general interference-freecommunication is achieved by using different frequencies for different communication channels. However,the number of available frequency ranges is limited so
it is impossible to assign a unique frequency to every
communication channel. A more clever frequencyassignment scheme is therefore needed. Finding aproper assignment of frequencies is often modeled as
the problem of computing a so-called conflict-free coloring, or CF-coloring for short, where different colors
represent different frequencies.
In this paper we look at the problem of finding a
CF-coloring with respect to disks for a set P of points
in the plane. That is, we want to assign colors to thepoints of P so that every disk D containing at least
one point of P contains a unique color. More formally,
we want to assign a color color (p) to each point p ∈ P
so that the following property holds: for every disk D
containing at least one point of P , there is a pointp ∈ P ∩ D so that for any point q ∈ P ∩ D\{p} wehave color (p) 6= color (q). It is convenient to identify
the i-th color with the integer i. The goal is then tominimize the maximum color used in the CF-coloring.
∗ MdB is supported by the Netherlands Organisation for Scientific Research (NWO) and MR is supported by the SMART
project at Tohoku University.
† Department of Computer Science, TU Eindhoven, theNetherlands. mdberg@win.tue.nl‡ Graduate School of Information Sciences, Tohoku University, Japan. marcel@dais.is.tohoku.ac.jp

Marcel Roeloffzen‡

The problem was introduced by Even et al. [5] who
provide a framework for finding CF-colorings withrespect to disks and several other types of regions.
Their algorithm works by finding independent sets on
a sequence of Delaunay triangulations of subsets of P
and uses O(log n) colors, which is asymptotically optimal [5, 7]. Several variants of the problem have also
been studied. For example, Har-Peled et al. [6] provide a probabilistic algorithm that works for simple
regions with low union-complexity, as well as several
algorithms for special cases such as axis-aligned rectangles. They also study k-CF-coloring, which is a relaxation of a regular CF-coloring. In a k-CF-coloringeach region need not contain a unique color, but instead a color that occurs between 1 and k times in that
region. There are also several results for online CFcoloring, where points are added incrementally andmust be assigned a color when added without knowledge of points to come [2, 4]. Additional backgroundcan be found in a recent survey by Smorodinsky [8].
All these papers assume the transmitters are stationary and frequencies are assigned exactly once.
This may however not always be the case. For
mobile RFID scanners or networks of autonomous
robots, for example, the frequency assignment may
need to change as the transmitters move. Unfortunately changing the frequency of a transmitter is often undesirable as it may interrupt current communications with that transmitter. This leads us to study
the problem maintaining a conflict-free coloring in theso called Kinetic Data Structures (KDS) framework.
Following the KDS framework as introduced byBasch et al. [3] we assume that we know the trajectories of the points (at least in the short term). The
goal is now to maintain a CF-coloring of the points asthey move along these trajectories. In frequency assignment, changing the frequency of a transmitter isusually expensive. Therefore, we focus on keeping thenumber of recolorings low while using O(log n) colors.
We provide two algorithms for this, both based on
the algorithm by Even et al. [5]. For both algorithms
we provide a theoretical analysis and an experimental
analysis of the maximum number of colors used andof the number of recolorings.
2

The algorithms

First we describe the algorithm by Even et al. [5]for static points in more detail, as our kinetic algo-This is an extended abstract of a presentation given at EuroCG 2015. It has been made public for the benefit of the community and should be considered apreprint rather than a formally reviewed paper. Thus, this work is expected to appear in a conference with formal proceedings and/or in a journal.

31st European Workshop on Computational Geometry, 2015

rithms are based on this. The algorithm is recursive
and starts by computing the Delaunay triangulation
DT (P1 ) of the complete point set P1 := P . The next
step is to find a large independent set I1 ⊂ P1 in
DT (P1 ). All points in I1 receive color 1. On theset P2 := P1 \I1 a new Delaunay triangulation andindependent set I2 are computed, then the points inI2 receive color 2, and the algorithm proceeds with
P3 := P2 \I2 . This process is repeated until all points
are colored. If we compute the independent set in eachDT (Pi ) in a greedy manner, by considering the points
in order of increasing degree, we can guarantee that
|Ii | > |Pi |/6, which implies that the algorithm finishes
after O(log n) rounds. The proof that this procedure
produces a conflict-free coloring was given—in a moregeneral setting—by Even et al. [5].
Next we adapt the static algorithm to a kinetic
setting where points move along known constantcomplexity curves. From the above it is clear that aslong as none of the Delaunay triangulations change,
then the coloring remains conflict-free. However,as the points move the Delaunay triangulation canchange, namely when four points that form a quadrangle in the Delaunay triangulation become co-circular.
When this happens a diagonal of the quadrangle flips,
which may invalidate the independent set. Under
known motions these co-circularities are not difficult
to detect and kinetic data structures exist that maintain a Delaunay triangulation and support insertionand deletion of vertices [1]. Therefore we focus on repairing the independent sets when such a flip occurs.
We propose two different methods, a greedy method
and a lazy method.
In the following we describe what the two methods
do when a flip occurs between vertices within a quadrangle Q := Q(p, q, r, s), where the edge pr is replacedby qs. The quadrangle Q may exist in the Delaunay
triangulation of multiple consecutive levels, but onlyin the last level i where it occurs can one or more of
the points p, q, r, s be in the independent set. This
follows from the fact that a point in the independent
set of level i cannot occur in any level j > i. We denote this level by lev (Q) and use k to denote the total
number of colors used before recovering.
Lazy updates. In the lazy approach we check if the
new edge connects two points in the independent set,thus making the set no longer independent. If so, we
recolor one of the two conflicting vertices to a newcolor. As a result the independent set of each layer
will slowly become smaller compared to the total number of points in that layer. When the independent
set becomes too small, we completely recompute thestructure from that layer onward.
In more detail, let Q := Q(p, q, r, s) denote thequadrangle within which the flip occurred, where edge

pr is replaced by qs. Let i := lev (Q). When the edge
pr flips to edge qs, we check if q and s are both in the
independent set Ii . If so, we remove one of the two,say q, from Ii , give it a new color k + 1 and add it toall sets Pj for i < j 6 k + 1. Note that any two points
that were independent in DT (Pj ) are still independent in DT (Pj ∪ {q}). Since we reduced Ii in size wecheck if it has become too small. More precisely, we
check if |Ii | < |Pi |/12, and if so we recolor Pi entirely
by running the static algorithm on Pi . We call this areset at level i. If we do not do a reset at level i, we
check if |Ij | < |Pj |/12 for some j > i. (This is needed
since we added q to all sets Pj for i < j 6 k + 1.) If
this is the case for some levels j, we do a reset at thesmallest such level j.
Lemma 1 Maintaining a CF-coloring with lazy updates ensures that we use at most O(log n) colors at
any time.
Proof. Each update guarantees that the sets Ii are
independent. Following the proof of Even et al. [5]this is enough to enough to show the coloring remain
conflict-free. Since we guarantee that each independent set Ii contains at least |Pi |/12 points at any time,O(log n) colors are used.

Our goal is to guarantee a CF-coloring using as few
recolorings as possible. Therefore, we now study the
number of recolorings that this method makes. It iseasy to see that a single flip in a Delaunay triangulation may cause Θ(n) recolorings: if a flip triggers areset of the first level, then all points may be recolored. However, this does not happen often since ourgreedy independent-set computation guarantees that
initially |Ii | > |Pi |/6, whereas we won’t reset until|Ii | < |Pi |/12. Most events—that is, flips in the Delaunay triangulation—do not cause many recolorings
and we can in fact prove that amortized only O(log n)recolorings happen per event.
Lemma 2 Each event triggers O(log n) recolorings
amortized.
Proof. We prove this using an accounting scheme,
where each point p has a wallet Wi (p) with a certain
amount of money, for every level i where it occurs.
To recolor a point it must pay e1. Thus, when doinga reset at level i, all points in Pi must pay e1. Next
we show that in each event we have to spend only
O(log n) euro to guarantee we can pay for all recolorings. We keep as an invariant that any point p inevery level i where it occurs has at least1−

12|Ii |
|Ii | − |Pi |/12
=2−
euros
|Pi |/12|Pi |in its wallet Wi (p). Note that since |Ii | > |Pi |/6 after
a reset at level i, the points need not have any money

EuroCG 2015, Ljubljana, Slovenia, March 16–18, 2015

immediately after a reset. Moreover, a reset occurs
when |Ii | < |Pi |/12, so then each point has at leaste1 and can pay for its recoloring.
Next we show we need to spend no more thanO(log n) euro per event to maintain the invariant.
Consider an event that causes point q to be removed
from the independent set Ii and added to a new level
Pk+1 . The wallets for points in levels j < i do notchange as the set Pj and Ij do not change. In level ithe size of Pi remains the same, but Ii becomes one
smaller. Let Ii and Pi denote the independent set andcomplete set of points in level i before the event andIi0 and Pi0 the same sets after the event. Before theevent we know that each point p ∈ Pi has at least2 − 12|Ii |/|Pi | euro. After the event it should have atleast 2 − 12|Ii0 |/|Pi0 | = 2 − 12(|Ii | − 1)/|Pi | euro. To
ensure this we must give each point at most 12/|Pi |euro, so at most e12 in total for all points in level i.
The money to be payed to levels j > i is calculated
as follows. Before the event each point in level j has
at least 2−12|Ij |/|Pj | euro and after the event it musthave at least 2 − 12|Ij |/(|Pj | + 1) euro. This means
we should pay each point in Pj (not including q)
12|Ij |
12|Ij |
12
12|Ij |
−
=
6
euro.
|Pj |
|Pj | + 1
|Pj |(|Pj | + 1)
|Pj | + 1
Since we have to pay this to |Pj | points, this costs us
no more than e12 per level. Lastly we have not yet
filled the wallet for the point q in all the levels it has
been added to. However, in each level it requires atmost e1. In total we spend no more than e13 perlevel, so O(log n) euro in total.

Greedy updates. In the lazy approach we doO(log n) recolorings amortized per event, but in some
updates we may have to recolor all points. We cantry to avoid this worst-case behavior by keeping theindependent sets large. To this end, at each event
we not only remove a point from an independent set,
but we also try to add new points. We maintain as aninvariant that each independent set is a maximal independent set consisting only of points with degree lessthan 12. This produces an independent set Ii with
|Ii | > |Pi |/24, as at least half the vertices have degree less than 12 and choosing one of these eliminates
no more than 12 from becoming part of the independent set. Next we discuss the updates necessary tomaintain this invariant.
Consider an event that is a flip within quadrangle Q := Q(p, q, r, s), where the edge pr is replacedby edge qs. We denote by lev ∗ (Q) the first level(that is, with smallest index i) where this flip occurs.
When processing the event we start at lev ∗ (Q) andthen proceed to later levels. In each level we havethe following situation. We have a current set Pi
with Delaunay triangulation DT (Pi ) and two (possibly empty) sets Pi+ and Pi− . The set Pi+ contains

points that are “pushed down” from the parent level
because they are no longer in the independent set atthat level; the set Pi− contains points that are “pulledup” from the parent level because they have just been
added to the independent set at the parent level. We
then update the Delaunay triangulation by constructing DT ((Pi ∪Pi+ )\Pi− ), update the independent set Ii ,+−and construct the sets Pi+1
and Pi+1
by looking at thedifferences between old and new independent set Ii .
In more detail we proceed as follows. We startby computing DT ((Pi ∪ Pi+ ) \ Pi− ). Note that fori = lev ∗ (Q) we have Pi+ = Pi− = ∅, but the Delaunay triangulation still changes because of the flip in Q.
Let Pi∗ denote the set of points whose neighbor set haschanged, including the set Pi+ of new points. Now for
the points in Pi∗ ∩ Ii we test if they still have degree
below 12, otherwise we remove them from Ii . Then
we check if any two vertices remaining in the independent set are connected, and we remove one of them if
needed. We repeat this until no more connected pairs
exist, and we have obtained an independent set for
the new Delaunay triangulation. Next we make theindependent set maximal by greedily adding points
with degree less than 12 that are not connected toany points of the independent set. The resulting set
is the new independent set Ii . As already mentioned,+−
we then construct the sets Pi+1
and Pi+1
by looking at
the differences between old and new independent set
Ii . Note that the sets Pi+ and Pi− (and, hence, the set
Pi∗ of “affected points”) may grow as we go down thelevels. Unfortunately it seems hard to prevent this,which makes it difficult to bound the worst-case number of recolorings. Fortunately our experiments (seebelow) show that in practice the avalanche effect islimited and not too many recolorings occur per event.
3

Experimental results

We showed some basic theoretical bounds for thenumber of recolorings. However, especially for thegreedy approach it seems unlikely that in practice weneed many recolorings per step. We therefore implemented both algorithms in order to count the numberof recolorings. For our input we use sets of points
that move along straight lines within a bounding box.
To avoid points going outside the bounding box, theybounce back when hitting the edge of bounding box.
We ran our implementation of the two methods forsets of moving points ranging from 20 to 2000 points
and measure the number of recolorings per step as wellas the total number of colors used. For 100 points theresults can be found in Fig. 1. The results with otheramounts of points are summarized in Table 1 and are
based on a run of 10,000 events—that is, flips in anyof the Delaunay graphs.
The graphs of Fig. 1 clearly show the difference between the two methods. The lazy method has a very

31st European Workshop on Computational Geometry, 2015

Figure 1: Number of recolorings indicated in red and total number of colors used in green for the lazy (left) and
Figure(right)
1: Numberof recolorings
indicatedin redfrom
andnumberofcolorsusedinusedgreen
for thelazy
andFigure1:method.
Numberofrecolorings
indicatedin
redtotal
total number
colorsinforthe(left)lazyevents.
(left) andgreedyBotharemeasured
anand
instancewith100
movingpointsFigure5.1: of
Examplesofgreenthenumberofrecolorings(red)(red)and thFigure5.1:
Examplesofoverthe2500
numberof recoloringsangreedygreedy(right)(right)
method.
Both aremeasuredfrom aninstancewith 100
points.points.
method.
Both
are measured
froman instancewithmoving
100 moving

during2500 2500
events.
Upper
left: left:
BoundedIS algorithmwith w1
duringevents.
Upper
BoundedIS algorithm

n
20
50
100
200
500
1000
2000

avg
12.4
17.2
20.9
24.6
28.3
31.3
34.0

Lazy Updates
Greedy Updates
BoundedIS algorithmwith with
1000 1000
points.
In boththe Bounded
IS gBoundedISalgorithm
points.
In boththe Bounded#Colors#Recolorings#Colors#Recolorings
avg
avg
max
max
to
ascenduntilmax
the resetof logthelayer.
Lower
left: left:
MaximalIS
to ascend
until
the
reset
offirstthefirst layer.
Lower
Maxim
max log n log n total
max
avg
total
max
log n
n
Lower
right:
Maximalalgorithm
1000 1000
points.
IS algorithm
withpoints.
15
2.9
3.5 1232
20Lower
8.2 right:
10 Maximal
1.9 IS 2.3
6414 with12
22
3.0
3.8 1569
50 11.2
14
2.0
2.5
8036
19
28
3.1
4.2 2017
100 13.5
16
2.0
2.4
9834
24
31
3.2
4.1 2275
200 15.9
18
2.1
2.4 12034
27
Figure5.1 showssomesome
examplesof theFigure5.1 showsofthe progression
of nu
th
35
3.2
3.9 2879
337
19.1
21
2.1
2.3 examples
15248of the
34progressionofrecolorings
duringthese
experiments,
andTables
5.1
and
5.2
of
recolorings
duringthese
experiments,
andTables
5.1
an
38
3.1
3.8 4064
444 21.3
23
2.1
2.3 18406
62
experiments.
42
3.1
3.8 5659
696experiments.
23.5
25
2.1
2.3 22164
60

One Oneinteresting
patternin theis theis “staircasee↵ectinteresting
patternin figures
the figures
the “staircase
Bounded IS algorithm. Namely, the recoloring spikes seem t
Figure5.1: 5.1:
Examplesof theof recolorings
numberof twocolors(green)FigureExamplesof numberthe numberof therecolorings
(red)
and
the
numberofsubsequentcolors(green)endofthegraph.
Infact,
forlayerslayers
Li andthe(red)end
ofandthethegraph.
In
fact,
for
two
subsequent
Li L
ani+
during2500
events.
Upper
left: left:
BoundedISalgorithm
with100
points.
Upper
right:
during2500
events.
Upper
BoundedISalgorithm
with100
points.
Upper
right:
GeometryAppl.
8(3):365–380,
1998.
low
numberof recolorings
for most
events,butseveralto resetshortly
beforeLi resets.
The reason
that that
this occurs
is th
to resetshortly
beforeLi resets.
The reason
this occurs
Boundedalgorithm
withthat
1000
points.
In
theBoundedISgraphs
the
reset
size
appears
Bounded
ISrecolorings
algorithm
with1000
points.
boththeBoundedISgraphs
the
reset
size
appears
eventswith aISmany
correspondto both
re-In
[2]
A.
Bar-Noy,P.
Cheilaris,
S.
Olonetsky,
and
S.
of L
,
so
its
boundsbreak
shortly
beforeL’sboundsbreak.
This
of
L
,
so
its
boundsbreak
shortly
beforeL’sboundsbreak.
i
i
i
i
sets
topascendlevelsour reset
data
structure.
This
step-wise
to atascenduntilofuntil
theof theoffirstlayer.
Lower
left:
MaximalIS Online
algorithm
with100
points.
tothe resetthefirstlayer.
Lower
left:
Maximal
IS algorithm
with100
points.
Smorodinsky.
conflict-freecolorings
forhy- gives
smallerspike
shortly
beforea largespike,
which
gives
us theseincsmallerspike
shortly
beforea largespike,
which
us thesbehavior
isright:
alsoright:
found
in
theIS
total
of
colorspergraphs. Journal Combinatorics, Probability andLower
Maximalalgorithm
with1000
points.
Lower
MaximalISnumberalgorithm
with1000
points.
reset
of
the
first
layer
we
expectthe
spikes
to
start
small
again.
reset
of
the
first
layer
we
expectthe
spikes
to
start
small
aga
Computing 19(4):493–526, 2010.
used, which slowly goes up until a reset of one of theIt isofcoursea bitawastefulto havea layer
Li+1 Lrecolor
shortsItisof course
bit wastefulto havea layer
i+1 recolor
top levels is done. The greedy approach on the other[3] J. Basch, L.J. Guibasand, J. Hershberger. Datastrucof thepointsinLarerecolored
twice
in
a
row,
and
if
L
woL
of
the
pointsinLarerecolored
twice
in
a
row,
and
hand does not have this spiky behavior, and insteadmostmostii iftures for mobile data.
Ini Proc. 8th ACM-SIAM Symp.
many Figure
eventscause
between5
and20
recolorings,
but
Disc.
Alg.,
pages
747–756,
1997.
before
Li+1
L
would
not
have
tonumberrecoloragainagain
for aforwhile
beforeLthen
nottonumberrecolora
5.1 showssomesome
examplesof theofthenumbercolorsandhave
Figure5.1 shows
examplesof progression
theprogression
ofthenthenumberofcolors
and
i+1 L
i+1
i+1ofwould
rarelymorethan that.
It alsohas
the effectthat andthe andFigureshows
theaverageandmaximum
numberof colors
Figure
5.2
shows
the
and
maximum
number
of c
[4]
K.5.2
Chen,
A.
Fiat,
H.
Kaplan,M. results
Levy,
Matoušek,
of recolorings
duringthese
experiments,
Tables
5.1
and
5.2
show
theaverage
resultsof J.theseof recolorings
duringthese
experiments,
Tables
5.1
and
5.2
show
the
of these
total number of colors appears very stable.
E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, andexperiments.
experiments.
In Table 1 we see that in both cases the number ofU. Wagner. Online conflict-free coloring for intervals.
interesting
patternin Whattheis theis “staircasee↵ect”
appears
duringthe 2006.
interestingin figures
thefiguresthe SIAM“staircasee↵ect”
that
appears
duringthecolorsOne
usedOneis proportional
to pattern
log n.
is interestJournal
onthatComputing36(5):1342–1359,
32 32
Boundedalgorithm.
Namely,therecoloring
seemseemto getand bigger
towards
Bounded
ISalthoughalgorithm.
Namely,the recoloring
spikestobiggerget bigger
and bigger
towards
ing
thoughisISthat
the greedy
methoduses spikes[5] G. Even, Z. Lotker, D. Ron, S. Smorodinsky. Conflictless
both
ongraph.
averagemaximum,
requiresthecolors,
end
theof
Inand
fact,
for twolayerslayers
L
and
L
,
we
have
that
L
tends
the ofend
thegraph.
In
fact,
foritsubsequent
twosubsequent
L
and
L
,
we
have
that
L
i+1 i+1i i+1i+1 geometric regions
freei coloringsof simple
withtends
applimany
morerecoloringsonaverage.
This
shows
that
cationstoassignment
in cellular
networks.
to resetshortly
beforeLi resets.
The reason
that that
this occurs
is frequency
that
Li+1
“almost”
the sizeto resetshortly
beforeLi resets.
The reason
thisoccursis that
Lisi+1is “almost”
the sizethethe
two methods
is strictlybefore
better L
than
SIAM
Journalon Computing
2003.
of neither
Liof, soLiofitsboundsbreakbreakshortly
break.
This Thismeans
we expecta slightly, soits
boundsshortly
beforeLi ’s bounds
break.
means
we33(1):94–136,
expecta slightly
i ’s bounds
the other. If one can afford to do many recolorings ev[6] givesS.
andincreasing
S. Smorodinsky.
Conflict-freesmallerand
spike
shortly
beforenota largespike,using
whichwhichgives
usHar-Peledthese
increasing
resetreset
sizes.
AfterAfteracolor-a
spike
a largeus thesesizes.
ery nowsmallerthen,andshortly
one doesbefore
care
about spike,ing of points and simple regions in the plane. Discreteof thelayer
welazyexpecttheisspikes
tosmall
again.
reset
offirstthethen
first
layer
we
expectthe
spikesto start
small
again.
a resetfew morecolors,themethodbetteras start& Computational Geometry 34(1):47–70, 2005.
of iscoursea bitawastefulto haveaiflayer
Li+1 Lrecolor
shortly
beforeLi , since
it meansItof course
bitthewasteful
to haverecolorshortly
beforeLi , since
it means
it willItdoisfewer
recolorings.
On
other
hand,
thea layeri+1[7] J. Pach and G. Toth. Conflict-freecolorings. In Disgoal
is most
to
the
total
numberofcolors
very
small
most
of keep
theofpointsinL
arerecolored
twice
in
a
row,
and
if
L
would
have
brokenits
boundsthe points iin Li are recolored twice in a row,
if Li would havebrokenitsGoodmanbounds
creteandandi Computational
Geometry- The
orbeforeto avoidmany
recolorings
at a notsingleevent,
then
Pollack
Festschrift
Li+1
Li+1 Lwould
have
to recolor
againagain
for aforwhile.
before
Lthen
not
have
to recolora while.(S. Basu et al., eds.), Springer
i+1 then
i+1 would
the greedy method appears better.
Verlag,Berlin,pagesplotted
665–671,2003.
Figure5.2 showsthe averageand maximum
numberof colorsplottedagainstlog n.logThe
Figure5.2 showsthe averageand maximum
numberof colorsagainstn. TheTable 1: Number of colors used and recoloringsBounded
for n moving
points usingNamely,
lazy and greedy
updates. spikes seem to get
IS algorithm.
the recoloring

References[1] G. Albers, L.J. Guibas, J.S.B. Mitchell, and T. Roos.32
Voronoi diagrams of moving points. Int. J. Comput.

[8] S. Smorodinsky. Conflict-Free Coloring and its Applications. In Geometry - Intuitive, Discrete, and Convex (I. Bárány et al., eds.) Springer Verlag, Berlin,
32 2014.