Problemet med ett par närmaste punkter

Det närmaste parproblemet är ett  beräkningsgeometriproblem . Med tanke på n punkter i ett metriskt utrymme måste du hitta ett par punkter med det minsta avståndet mellan dem.

Det närmaste punktproblemet i det euklidiska planet [1] var ett av de första geometriska problemen som systematiskt studerades i termer av beräkningskomplexiteten hos geometriska algoritmer .

En naiv algoritm för att hitta avstånden mellan alla par i ett utrymme med dimension d och välja det minsta bland dem tar tid O ( n2 ) . Det visar sig att problemet kan lösas i tid i euklidiskt rum eller L p rum med fast dimension d [2] . I den algebraiska beslutsträdsberäkningsmodellen [ , är algoritmen med tiden O( n log n ) optimal när den reduceras från elementets unikhetsproblem . I en beräkningsmodell som antar att golvet -funktionen beräknas i konstant tid, kan problemet lösas i tid [3] . Om vi ​​tillåter att randomisering tillämpas tillsammans med golvfunktionen kan problemet lösas i O( n ) [4] [5] tid .

Brute force-algoritm

Paret av närmaste punkter kan beräknas i O ( n2 ) tid genom att utföra en fullständig uppräkning . För att göra detta kan du beräkna avståndet mellan alla n ( n − 1) / 2 par av punkter och sedan välja paret med det minsta avståndet, som visas nedan.

minDist = oändligt för i = 1 till längd( P ) - 1 för j = i + 1 till längd( P ) låt p = P [ i ], q = P [ j ] om dist ( p , q ) < minDist : minDist = dist ( p , q ) closestPair = ( p , q ) returnera closestPair

Planärt fall

Problemet kan lösas i tid genom att använda ett rekursivt dela-och-härska tillvägagångssätt , så här [1] :

  1. Sortera punkterna efter deras x-koordinater;
  2. Vi delar upp uppsättningen punkter i två delmängder av samma storlek som den vertikala linjen ;
  3. Vi löser problemet rekursivt på vänster och höger sida. Detta resulterar i ett vänster minimiavstånd respektive ett höger minimiavstånd ;
  4. Vi finner det minsta avståndet mellan par av punkter, varav en punkt ligger till vänster om den vertikala linjen och den andra punkten ligger till höger om den räta linjen;
  5. Det slutliga svaret kommer att vara det lägsta värdet bland , och .

Det visar sig att steg 4 kan genomföras i linjär tid. Återigen skulle det naiva tillvägagångssättet kräva beräkningsavstånd för alla vänster/höger-par, d.v.s. kvadratisk tid. Nyckelobservationen är baserad på följande sparsitetsegenskap för uppsättningen av punkter. Vi vet redan att det närmaste paret av punkter inte är längre ifrån varandra än . Därför måste vi för varje punkt p till vänster om skiljelinjen jämföra avstånden med punkter som ligger i en rektangel med dimensioner (avstånd, 2 ⋅ dist) som visas i figuren. Och den här rektangeln får inte innehålla mer än sex punkter, vars avstånd i par är inte mindre än . Det räcker alltså att beräkna 6 n avstånd i det 4:e steget [6] . Upprepningsrelationen för antalet steg kan skrivas som , vilket kan lösas med hjälp av grundsatsen för dividera och erövre recurrence , som ger .

Eftersom ett par av närmaste punkter definierar en kant i en Delaunay-triangulering och motsvarar två intilliggande celler i ett Voronoi-diagram , kan ett par av närmaste punkter bestämmas i linjär tid om en av de två strukturerna ges. Att beräkna en Delaunay-triangulering eller ett Voronoi-diagram tar tid . Dessa tillvägagångssätt är inte effektiva för dimensioner d >2 , medan dividera och erövra-algoritmen kan generaliseras till körtid för vilket konstant värde som helst av dimensionen d .

Dynamiskt problem med närmaste par

Den dynamiska versionen för problemet med ett par närmaste punkter är inställd enligt följande:

Om begränsningsrutan för alla punkter är känd i förväg och en golvfunktion med konstant gångtid är tillgänglig, så föreslogs en datastruktur med ett förväntat minne på O( n ) som stöder en förväntad tid (medeltid) för insättning och radering av O(log n ) och en konstant frågetid . Om problemet modifieras för en algebraisk beslutsträdsmodell kommer infogning och borttagning att kräva en genomsnittlig tid [7] . Det bör noteras att komplexiteten hos ovanstående dynamiska problem med ett par närmaste punkter exponentiellt beror på dimensionen d , så algoritmen blir mindre lämplig för högdimensionella problem.

En algoritm för det dynamiska problemet med ett par närmaste punkter i ett utrymme med dimension d utvecklades av Sergey Bespamyatnykh 1998 [8] . Punkter kan infogas och tas bort i O(log n ) tid per punkt (värsta fall).

Se även

Anteckningar

  1. ↑ 1 2 Shamos, Hoey, 1975 , sid. 151-162.
  2. ↑ Clarkson, 1983 .
  3. ↑ Fortune, Hopcroft, 1979 , sid. 20-23.
  4. ↑ Khuller och Matias 1995 , sid. 34-37.
  5. ↑ Richard Lipton. Rabin slår ett mynt (24 september 2011). Hämtad 19 februari 2019. Arkiverad från originalet 16 februari 2019.
  6. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , sid. 957-961 33.4: Hitta det närmaste poängparet..
  7. ↑ Golin, Raman, Schwarz, Smid, 1998 .
  8. ↑ Bespamyatnikh, 1998 , sid. 175-195.

Litteratur