Svepande linjealgoritm

Den svepande linjealgoritmen eller plansvepningsalgoritmen  är ett algoritmiskt paradigm som använder en spekulativ sveplinje eller svepyta för att lösa olika problem i det euklidiska rymden . Detta är en av nyckelteknikerna inom beräkningsgeometri.

Tanken med algoritmer av denna typ är att föreställa sig en imaginär rak linje (vanligtvis vertikal) som rör sig längs planet och stannar vid vissa punkter. Geometriska operationer är begränsade till geometriska objekt som antingen skär eller gränsar till den svepande linjen, och den fullständiga lösningen är tillgänglig när linjen passerar genom alla objekt.

Historik

Detta tillvägagångssätt kan spåras tillbaka till linjeavsökningsalgoritmer i datorgrafik , sedan användes detta tillvägagångssätt i tidiga integrerade kretslayoutalgoritmer , där den geometriska beskrivningen av en integrerad krets utfördes i form av parallella remsor, eftersom den fullständiga beskrivningen inte fick plats i minnet.

Applikationer

Tillämpningen av detta tillvägagångssätt ledde till ett genombrott i beräkningskomplexiteten för geometriska algoritmer när Shamos och Howey presenterade algoritmer för korsande linjesegment i planet, och i synnerhet beskrev de hur man kombinerar skanningslinjemetoden med effektiva datastrukturer ( balanserade binära träd ) gör det möjligt att detektera om det finns skärningar av N segment i planet, med komplexitet O [1] . Den närbesläktade Bentley-Ottmann-algoritmen använder svepande linjeteknik för att erhålla alla K skärningspunkter mellan alla N linjesegment i ett plan med tids- och minneskomplexitet [2] .

Sedan dess har detta tillvägagångssätt använts för att utveckla effektiva algoritmer för ett antal problem, såsom konstruktionen av ett Voronoi-diagram ( Fortunes algoritm ) och Delaunay-triangulering eller booleska operationer på polygoner .

Generaliseringar och tillägg

Topologisk balayage är en typ av plan balayage som lättar på kraven på ordningen av bearbetade punkter, vilket undviker en fullständig sortering av punkter och gör att sveplinjealgoritmen kan arbeta mer effektivt.

Den roterande bromsoktekniken för att konstruera geometriska algoritmer kan också tolkas som en sorts balayage i det projektiva dubbelplanet — projektiv dualitet omvandlar lutningen på en linje i planet till x -koordinaten för en punkt i dubbelplanet, så att linjens passage sorteras efter dess lutning. Processen för den roterande tjockleksalgoritmen är således den dubbla processen att passera genom punkter sorterade efter deras x -koordinater i den plana balayage-algoritmen.

Det svepande tillvägagångssättet kan generaliseras till högre dimensioner.

Anteckningar

  1. ↑ Shamos och Hoey 1976 , sid. 208–215.
  2. ↑ Souvaine, 2008 .

Litteratur