Jordan-reeks

In de wiskunde wordt een Jordan-reeks gevormd door de abscissen van de snijpunten van een Jordan-kromme met de $x$-as, opgelijst in de volgorde waarin ze voorkomen op de kromme. Conventioneel en zonder verlies van algemeenheid wordt het begin van de kromme onder de $x$-as verondersteld (eventueel wordt de kromme eerst gespiegeld omheen de $x$-as). De kromme en de $x$-as vormen een meander.

Hieronder is een voorbeeld weergegeven:

De kromme begint bij punt 5 en eindigt bij punt 8. Zoals elke Jordan-kromme kruist ze zichzelf nergens. Ze raakt ook nergens aan de $x$-as. De bijhorende Jordan-reeks is dan $x_{5},x_{4},x_{6},\ldots ,x_{9},x_{8}$.

Indien de Jordan-reeks bestaat uit de natuurlijke getallen 1 tot en met $n$ in een bepaalde volgorde, wordt ze een Jordan-permutatie genoemd. De reeks 5, 4, 6, 3, 2, 1, 7, 11, 10, 9, 8 is een Jordan-permutatie. Niet elk van de $n!$ mogelijke permutaties is een geldige Jordan-permutatie. Er zijn ten hoogste $c_{n}$ geldige Jordan-permutaties van 1 tot $n,$ waarbij $c$ een constante is die onafhankelijk is van $n.$

Twee opeenvolgende getallen $x_{i-1}$en $x_{i}$ in de reeks corresponderen met een gedeelte van de kromme dat ofwel boven de $x$-as verloopt (dit zijn de paren 5-4, 6-3, 2-1, 7-11 en 10-9), ofwel eronder (de paren 4-6, 3-2, 1-7, 11-10 en 9-8). In het eerste geval is de index $i$ even en in het tweede geval is $i$ oneven. In de gesorteerde reeks vormen die paren intervallen die ofwel gescheiden zijn van elkaar ofwel volledig gelegen zijn in een ander interval. Ze mogen elkaar niet gedeeltelijk overlappen. In dit geval is het interval 4-5 vervat in 3-6, 9-10 in 7-11, en 2-3 en 4-5 in 1-7. Immers elk van deze intervallen komt overeen met een boog van de kromme tussen twee opeenvolgende snijpunten van de kromme met de $x$-as en is dus het interval van de $x$-as dat deze boog overspant. Uit het feit dat een Jordan-kromme zichzelf niet snijdt volgt dat twee bogen elkaar niet mogen snijden en dat de overeenkomstige intervallen elkaar niet mogen overlappen. Hierbij moeten de bogen boven de $x$-as en die eronder apart beschouwd worden. (Daarom is de reeks 5, 3, 6, 4, 2, 1, 7, ... geen geldige Jordan-permutatie: in de gesorteerde reeks 1, 2, 3, 4, 5, 6, 7,... zijn de intervallen 3-5 en 4-6 niet ineengenest of gescheiden maar overlappen ze elkaar. Als men de bijhorende kromme tekent zal men zien dat die zichzelf kruist.)

Men kan de overlappende intervallen ook voorstellen door een verzameling van ineengeneste haakjes. Voor de bogen boven de $x$-as schrijven we een "(" bij het kleinste en een ")" bij het grootste van de twee getallen die door een boog verbonden zijn (het laatste punt op de kromme, dit is hier punt 8, slaan we over omdat daarvandaan geen bovenboog vertrekt). Dit geeft in ons voorbeeld:

  1  2  3  4  5  6  7  8  9 10 11
  (  )  (  (  )  )  (     (  )  )

Op dezelfde manier kunnen we de bogen onder de $x$-as voorstellen door een verzameling geneste haakjes (nu laten we het beginpunt, punt 5, weg):

  1  2  3  4  5  6  7  8  9 10 11
  (  (  )  (     )  )  (  )  (  )

Dit kan men ook voorstellen in een boomstructuur.

Jordan-reeksen komen in de computerwetenschap voor; daarbij stelt zich het probleem hoe Jordan-reeksen te herkennen en snel van klein naar groot te sorteren. Een Jordan-reeks kan gesorteerd worden met $O(n)$ vergelijkingen van twee getallen. Hieruit volgt dat het mogelijk is om een Jordan-reeks in lineaire tijd te sorteren.

De $x$-as kan ook vervangen worden door een willekeurige rechte of door een andere Jordan-kromme; het probleem wordt dan: gegeven de snijpunten van twee Jordan-krommen $A$ en $B,$ in de volgorde waarin ze voorkomen op kromme $A,$ sorteer ze in de volgorde waarin ze voorkomen op $B.$ Dit probleem komt voor in de computationele geometrie.

Bronnen, noten en/of referenties