Draadloze netwerken, bijvoorbeeld voor mobiele telefonie, bestaan uit basis-stations (zendmasten) die de communicatie voor gebruikers van het netwerk verzorgen. Als een gebruiker binnen bereik is van meerdere zendmasten, dan heeft hij in principe meerdere mogelijkheden ter beschikking om de communicatie te laten verlopen. Als verschillende zendmasten echter dezelfde frequentie gebruiken, dan kan de communicatie met die zendmasten verstoord worden door interferentie. Dit kan natuurlijk voorkomen worden door elke zendmast een eigen, unieke frequentie toe te kennen, maar het uitgeven van veel verschillende frequenties is ongewenst. De vraag is dus: is het echt nodig om alle zendmasten een eigen frequentie te geven, of kunnen we ook met minder frequenties toe? In dit artikel zullen we zogenaamde conflict-vrije kleuringen bekijken, die het bovenstaande probleem modelleren.

In onze modellering gaan we er vanuit dat een zendmast alle gebruikers kan bereiken binnen een gegeven vaste afstand. (Dit is in praktijk niet precies het geval: het bereik van een zendmast wordt onder andere beïnvloed door gebouwen en atmosferische omstandigheden, en sommige zendmasten kunnen krachtiger dan andere zijn.) In ons model is het bereik van een zendmast dus een schijf met de zendmast als middelpunt en met een vaste straal. Het toekennen van een frequentie aan een zendmast wordt nu gemodelleerd als het toekennen van een kleur aan de bijbehorende schijf, waarbij we voor het gemak de $i$-de kleur identificeren met de integer $i$. Dit leidt tot het volgende abstracte probleem.

Laat $\mathcal{S} := \{S_1,\ldots,S_n\}$ een verzameling van $n$ schijven in het vlak zijn, elk met dezelfde straal. Voor een punt $q\in \mathbb{R}^2$ definiëren we $\mathcal{S}(q) := \{ S_i \in \mathcal{S} : q\in S_i \}$ als de verzameling schijven die $q$ bevatten.

Een kleuring van $\mathcal{S}$ met $c$ kleuren is een afbeelding $\kappa$ die aan elke schijf $S_i\in\mathcal{S}$ een kleur $\kappa(S_i)\in \{1,\ldots,c\}$ toekent. Een kleuring $\kappa$ wordt conflict-vrij genoemd als het volgende geldt voor elk punt $q\in \mathbb{R}^2$: als $\mathcal{S}(q)\neq \emptyset$ dan is er een schijf in $\mathcal{S}(q)$ met een unieke kleur, dat wil zeggen een schijf $S_i\in \mathcal{S}(q)$ zodanig dat $\kappa(S_j) \neq \kappa(S_i)$ voor alle $S_j\in \mathcal{S}(q)\setminus \{S_i\}$. In de toepassing die we in gedachten hebben zou een gebruiker op locatie $q$ dus kunnen communiceren via de zendmast behorend bij $S_i$, want alle andere zendmasten die binnen bereik zijn gebruiken een andere frequentie. Figuur 1 illustreert het concept van conflict-vrije kleuringen.

De vraag die we nu willen beantwoorden is: wat is het kleinste aantal kleuren, als functie van $n$, zodat we voor elke verzameling $\mathcal{S}$ van $n$ schijven een conflict-vrije kleuring kunnen vinden? Wat formeler: als $\chi_{\mathrm{cf}}(\mathcal{S})$ het minimale aantal kleuren is dat nodig is om $\mathcal{S}$ conflict-vrij te kleuren, dan willen we

$$\chi_{\mathrm{cf}}(n) := \max_{|\mathcal{S}|=n} \chi_{\mathrm{cf}}(\mathcal{S})$$

bepalen.

Conflict-vrije kleuringen zijn gerelateerd aan graaf-kleuringen. In een gewone graaf-kleuring moeten de knopen van een graaf op een zodanige manier gekleurd worden dat de eindpunten van elke kant in de graaf verschillend gekleurd zijn. De beroemde Vier-Kleuren Stelling zegt dat elke planaire graaf met vier kleuren gekleurd kan worden. Laat $G_{\mathcal{S}}$ nu de intersectie-graaf van $\mathcal{S}$ zijn, dat wil zeggen de graaf met een knoop voor elke schijf $S_i\in \mathcal{S}$ en een kant tussen twee schijven $S_i$ en $S_j$ als $S_i \cap S_j \neq \emptyset$. Dan geeft een kleuring van de graaf $G_{\mathcal{S}}$ een conflict-vrije kleuring van de schijven. Immers, voor elk punt $q\in \mathbb{R}$ snijden alle schijven in $\mathcal{S}(q)$ elkaar, dus alle schijven in $\mathcal{S}(q)$ moeten verschillend gekleurd zijn. Helaas is de intersectie-graaf van een verzameling schijven niet noodzakelijk planair. Sterker, als alle schrijven elkaar snijden dan is de intersectie-graaf $\mathcal{G}$ een volledige graaf en zijn er dus $n$ kleuren nodig voor een gewone kleuring van $G_{\mathcal{S}}$. Dit betekent niet dat een conflict-vrije kleuring van $\mathcal{S}$ in dit geval ook $n$ kleuren nodig heeft. Zo zijn de linker vier schijven in Figuur 1 conflict-vrij gekleurd met drie kleuren, terwijl de intersectie-graaf van deze vier schijven volledig is. We zullen zien dat, hoe de schijven ook liggen, er altijd een conflict-vrije kleuring bestaat met maar $O(\log n)$ kleuren.

Het 1-dimensionale geval

Om meer inzicht in het probleem te krijgen bestuderen we eerst de 1-dimensionale versie, waarbij een verzameling $\mathcal{I}:=\{I_1,\ldots,I_n\}$ van $n$ intervallen in $\mathbb{R}^1$ conflict-vrij gekleurd moet worden. Een conflict-vrije kleuring is hier gedefinieerd analoog aan het 2-dimensionale geval: voor elk punt $q\in \mathbb{R}^1$ moet gelden dat $\mathcal{I}(q)$, de verzameling van intervallen die $q$ bevatten, ten minste één interval heeft met een kleur die uniek is binnen $\mathcal{I}(q)$. Het blijkt dat er in deze 1-dimensionale versie maar drie kleuren nodig zijn voor een conflict-vrije kleuring. Het volgende algoritme genereert zo'n kleuring. We gaan er in de beschrijving voor het gemak vanuit dat de er geen eindpunten van intervallen samenvallen; het is niet moeilijk om het algoritme aan te passen als dit wel zo is.

Laat $I_1$ het interval zijn met het meest linkse linker eindpunt. We geven interval $I_1$ kleur 1 en kleuren daarna de overige intervallen als volgt.

Laat $\mathcal{I}^*$ de verzameling intervallen zijn die nog gekleurd moeten worden, en laat $I^*$ het meest rechtse al gekleurde interval zijn. In het begin geldt dus $\mathcal{I}^* = \mathcal{I}\setminus \{I^*\}$ en $I^* =I_1$, maar in de loop van het algoritme zullen intervallen uit $\mathcal{I}^*$ verwijderd worden en zal $I^*$ veranderen. We zullen er echter voor zorgen dat $I^*$ altijd kleur 1 of 2 heeft. Bekijk nu alle intervallen in $\mathcal{I}^*$ die hun linker eindpunt in $I^*$ hebben. Laat $\mathcal{I}_{\mathrm{in}}$ deze verzameling intervallen zijn. Er zijn twee gevallen, geïllustreerd in Figuur 2.

1. Als $\mathcal{I}_{\mathrm{in}}$ ten minste één interval bevat dat niet helemaal binnen $I^*$ ligt, laat dan $I_j\in \mathcal{I}_{\mathrm{in}}$ het interval zijn dat het verst naar rechts uitsteekt. We kleuren $I_j$ als volgt: $\kappa(I_j) := 2$ als $\kappa(I^*)=1$ en $\kappa(I_j) := 1$ als $\kappa(I^*)=2$. Alle andere intervallen in $\mathcal{I}_{\mathrm{in}}$ krijgen kleur 3. Tenslotte verwijderen we de zojuist gekleurde intervallen uit $\mathcal{I}^*$, en veranderen we $I^*$ in $I_j$.
2. Als alle intervallen in $\mathcal{I}_{\mathrm{in}}$ bevat zijn in het interval $I^*$ --- het geval $\mathcal{I}_{\mathrm{in}}=\emptyset$ valt hier onder---, geef dan deze intervallen kleur 3 en verwijder ze uit $I^*$. Neem daarna van alle overblijvende intervallen in $\mathcal{I}^*$ het interval $I_j$ met het meest linkse linker eindpunt, geef $I_j$ kleur 1, verwijder $I_j$ uit $\mathcal{I}^*$, en verander $I^*$ in $I_j$.

Nadat we het relevante geval hebben afgehandeld wordt het proces herhaald met de nieuwe $\mathcal{I}^*$ en $I^*$, net zolang tot $\mathcal{I}^*=\emptyset$ en dus alle intervallen gekleurd zijn. Dit leidt tot de volgende stelling.

Het 2-dimensionale geval

Het 2-dimensionale geval, waarin we schijven in het vlak willen kleuren, is een stuk lastiger dan het 1-dimensionale geval. Zoals eerder aangegeven zullen we aannemen dat alle schijven in $\mathcal{S}$ dezelfde straal hebben. Zelfs dan blijkt het niet altijd mogelijk om een conflict-vrije kleuring te geven met een constant aantal kleuren.

Gelukkig wordt het niet veel erger dan in bovenstaande stelling: elke verzameling van $n$ even grote schijven kan conflict-vrij gekleurd worden met $O(\log n)$ kleuren. Het algoritme hiervoor gebruikt de Delaunay triangulatie, die we kort introduceren voordat we het algoritme beschrijven.

De Delaunay triangulatie.

Laat $\mathcal{P}$ een verzameling van $n$ punten in het vlak zijn. Een triangulatie van $\mathcal{P}$ is een verdeling van de convex hull van $\mathcal{P}$ in driehoeken, waarbij de verzameling hoekpunten van de driehoeken gelijk is aan $\mathcal{P}$. Een bijzondere triangulatie is de Delaunay triangulatie, genoemd naar de Russische wiskundige Boris Delaunay (1890--1980). De Delaunay triangulatie $\mathrm{DT}(P)$ wordt verkregen door een lijnstuk te trekken tussen elk paar punten $p_i,p_j\in P$ dat de lege-cirkel eigenschap heeft: er is een cirkel $C$ met $p_i$ en $p_j$ op de rand die verder leeg is, dat wil zeggen, die geen andere punten van $\mathcal{P}$ bevat in het inwendige of op de rand (Als er vier of meer punten van $\mathcal{P}$ precies op een cirkel liggen, dan hoeft het verbinden van alle paren met de lege-cirkel eigenschap geen volledige triangulatie op te leveren. Indien gewenst kan een volledige triangulatie verkregen worden door het toevoegen van een aantal extra verbindingen, maar voor onze toepassing is dat niet nodig), zie Figuur 3.

De Delaunay triangulatie wordt voor allerlei toepassingen gebruikt en heeft prachtige eigenschappen. Zo is de Delaunay triangulatie de duale van het bekende Voronoi diagram: twee punten $p_i,p_j$ zijn verbonden in $\mathrm{DT}(P)$ dan en slechts dan als de Voronoi cellen van $p_i$ en $p_j$ buren zijn in $\mathrm{Vor}(P)$. (Het Voronoi diagram $\mathrm{Vor}(P)$ is de opdeling van het platte vlak in Voronoi cellen, één per punt $p_i\in P$, zodanig dat de cel van $p_i$ precies die punten $q\in \mathbb{R}^2$ bevat waarvoor $p_i$ het dichtstbijzijnde punt in $\mathcal{P}$ is). Voor ons zijn maar twee eigenschappen van de Delaunay triangulatie van belang: de lege-cirkel eigenschap en het feit dat $\mathrm{DT}(P)$ een planaire graaf is (met $\mathcal{P}$ als de verzameling knopen, en de verbindingen tussen de punten als kanten).

Een conflict-vrije kleuring met behulp van de Delaunay triangulatie.

We keren nu terug naar het kleuringsprobleem voor een verzameling $\mathcal{S}$ van even grote schijven in het vlak. We zullen dit probleem eerst transformeren naar een kleuringsprobleem op punten.

Laat $p_i$ het middelpunt van de schijf $S_i\in \mathcal{S}$ zijn, en laat $\mathcal{P} := \{p_i : S_i\in \mathcal{S}\}$ de verzameling van alle middelpunten zijn. Laat $r$ de gemeenschappelijk straal zijn van de schijven in $\mathcal{S}$. Merk op dat voor elk punt $q\in \mathbb{R}^2$ en elke schijf $S_i \in\mathcal{S}$ geldt dat $q\in S_i$ dan en slechts dan als $p_i\in D_q$, waarbij $D_q$ de schijf is met middelpunt $q$ en straal $r$. Definieer $\mathcal{P}(D_q)$ als de verzameling van punten $p_i\in \mathcal{P}$ die in $D_q$ liggen. Dan is het vinden van een conflict-vrije kleuring voor $\mathcal{S}$ equivalent aan het vinden van een conflict-vrije kleuring voor $\mathcal{P}$, waarbij een kleuring voor $\mathcal{P}$ conflict-vrij is als het volgende geldt voor elk punt $q\in \mathbb{R}^2$: als $\mathcal{P}(D_q)\neq \emptyset$ dan is er een punt $p_i\in \mathcal{P}(D_q)$ met een unieke kleur. De Delaunay triangulatie geeft een elegant algoritme om een conflict-vrije kleuring voor $\mathcal{P}$ te vinden, zoals hieronder beschreven.

Het algoritme werkt in $O(\log n)$ fasen. In de eerste fase geven we een aantal punten kleur 1, in de tweede fase geven we een aantal punten kleur 2, enzovoorts, totdat alle punten een kleur hebben gekregen. Het selecteren van de punten die in de $k$-de fase gekleurd worden, gaat als volgt.

Laat $\mathcal{P}_k\subseteq \mathcal{P}$ de deelverzameling van de punten zijn die nog geen kleur hebben gekregen, en laat $\mathrm{DT}(\mathcal{P}_k)$ de Delaunay triangulatie van $\mathcal{P}_k$ zijn. Een independent set in $\mathrm{DT}(\mathcal{P}_k)$ is een deelverzameling van punten uit $\mathcal{P}_k$ die niet met elkaar verbonden zijn in $\mathrm{DT}(\mathcal{P}_k)$; zie Figuur 4.

Omdat $\mathrm{DT}(\mathcal{P}_k)$ een planaire graaf is, heeft $\mathrm{DT}(\mathcal{P}_k)$ een independent set $\mathcal{I}_k$ met ten minste $n_k/4$ punten. We selecteren de punten in $\mathcal{I}_k$ als de punten die kleur $k$ krijgen. De verzameling $\mathcal{P}_{k+1}$ die voor volgende fase overblijft, is dus $\mathcal{P}_k\setminus \mathcal{I}_k$.

Nadat we alle punten uit $\mathcal{P}$ gekleurd hebben volgens het bovenstaande algoritme, geven we elke schijf $S_i\in \mathcal{S}$ de kleur van het bijbehorende middelpunt. Dit leidt tot het volgende resultaat.

Slotopmerkingen

Conflict-vrije kleuringen werden in 2003 geïntroduceerd door Even et al.[1], die onder andere bewezen dat elke verzameling van $n$ schijven met $O(\log n)$ kleuren conflict-vrij gekleurd kan worden. Hun bewijs is een stuk algemener dan de versie die we hier besproken hebben. Het werkt bijvoorbeeld ook voor verzamelingen pseudo-disks, dat wil zeggen verzamelingen van samenhangende gebieden zodanig dat de randen van elk paar gebieden elkaar maar in ten hoogste twee punten snijden. Sinds 2003 zijn er veel varianten van conflict-vrije kleuringen bestudeerd; Smorodinski [2] geeft een overzicht van het werk op dit gebied. Toch zijn nog lang niet alle vragen beantwoord. Zo is het ondergrens-voorbeeld van Stelling 2 niet erg realistisch: in de praktijk zullen de de zendmasten nooit zo dicht bij elkaar geplaatst worden. Dat leidt bijvoorbeeld tot de vraag: met hoeveel kleuren kunnen we toe als geen enkel punt in het vlak binnen bereik is van meer dan $k$ van de $n$ zendmasten, voor $k\ll n$? Het voorbeeld van Figuur 2 laat zien dat er in dit geval soms $\Omega(\log k)$ kleuren nodig zijn, maar er een goede bovengrens is niet bekend. Zelfs voor het geval dat elke schijf maar $k$ andere schijven snijdt is de best bekende bovengrens $O(\log^2 k)$ [2]. Ook over andere meer realistische modellen, bijvoorbeeld waarin er rekening mee wordt gehouden dat obstakels het bereik van de zendmasten kunnen beïnvloeden, is weinig bekend. Kortom: nog veel uitdagingen voor onderzoek!

Referenties

Dit artikel is eerder verschenen in "Nieuw Archief voor Wiskunde" 5e serie, deel 3, nummer 16. The Network Pages dankt NAW voor permissie.

1. G. Even, Z. Lotker, D. Ron, and S. Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33:94-136 (2003).
2. S. Smorodinski, Conflict-Free Coloring and its Applications, In: I. Barany, K.J. Boroczky, G. Fejes Toth, and J.Pach (eds.) Geometry - Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies 24, pp. 331-389, Springer, 2013.