Längst-första traversering

De första fem punkterna i en längst-första genomgång av en plan punktuppsättning. Den första punkten väljs godtyckligt och varje efterföljande punkt är så långt som möjligt från alla tidigare valda punkter.

I beräkningsgeometri är den längst borta första genomgången av ett kompakt metriskt utrymme en sekvens av punkter i utrymmet, där den första punkten väljs godtyckligt och varje efterföljande punkt är så långt som möjligt från uppsättningen av tidigare valda punkter. Samma koncept kan också tillämpas på en ändlig uppsättning geometriska punkter, genom att begränsa de valda punkterna till att tillhöra mängden eller motsvarande genom att beakta det ändliga metriska utrymmet som genereras av dessa punkter. För ett ändligt metriskt utrymme eller ändlig uppsättning geometriska punkter, bildar den resulterande sekvensen en permutation av punkterna, även känd som den giriga permutationen .

Varje prefix för en längst bort-först genomgång ger en uppsättning punkter som är brett åtskilda och nära alla återstående punkter. Mer exakt kan ingen annan uppsättning med lika många punkter fördelas mer än dubbelt så brett, och ingen annan uppsättning med lika många punkter kan vara mindre än hälften så långt till sin längsta återstående punkt. Delvis på grund av dessa egenskaper, har längst bort punkt genomgångar många tillämpningar, inklusive approximation av resande säljare problemet och metriska k -center problemet. De kan konstrueras i polynomtid , eller (för lågdimensionella euklidiska rum ) approximeras i nästan linjär tid .

Definition och egenskaper

En längst-först genomgång är en sekvens av punkter i ett kompakt metriskt utrymme , där varje punkt visas högst en gång. Om utrymmet är ändligt, visas varje punkt exakt en gång, och genomgången är en permutation av alla punkter i utrymmet. Den första punkten i sekvensen kan vara vilken punkt som helst i utrymmet. Varje punkt p efter den första måste ha största möjliga avstånd till uppsättningen av punkter tidigare än p i sekvensen, där avståndet från en punkt till en uppsättning definieras som det minsta av de parvisa avstånden till punkter i mängden. Ett givet utrymme kan ha många olika längst-först genomgångar, beroende både på valet av den första punkten i sekvensen (som kan vara vilken punkt som helst i utrymmet) och på band för det maximala avståndet mellan senare val.

De längsta punkterna kan karakteriseras av följande egenskaper. Fixa ett tal k och betrakta prefixet som bildas av de första k punkterna i den längst borta och första genomgången av ett metriskt utrymme. Låt r vara avståndet mellan prefixets slutpunkt och de andra punkterna i prefixet. Då har denna delmängd följande två egenskaper:

• Alla par av de valda punkterna är på avstånd minst r från varandra, och
• Alla punkter i det metriska utrymmet är på avstånd högst r från delmängden.

Omvänt måste varje sekvens som har dessa egenskaper, för alla val av k , vara en längst-först genomgång. Dessa är de två definierande egenskaperna för en Delone-uppsättning , så varje prefix av den längst borta-första genomgången bildar en Delone-uppsättning.

Ansökningar

Rosenkrantz, Stearns & Lewis (1977) använde längst-först-traversalen för att definiera heuristiken längst bort för det resande säljarproblemet . Denna heuristik hittar ungefärliga lösningar på resandeförsäljarproblemet genom att bygga upp en tur på en delmängd av punkter, lägga till en punkt i taget till turnén i den ordning som ges av en längst-först genomgång. För att lägga till varje punkt till turen bryts en kant av den föregående turen och ersätts av ett par kanter genom den tillagda punkten, på billigast möjliga sätt. Även om Rosenkrantz et al. bevisa endast ett logaritmiskt approximationsförhållande för denna metod visar de att det i praktiken ofta fungerar bättre än andra insättningsmetoder med bättre bevisbara approximationsförhållanden.

Senare populariserades samma sekvens av punkter av Gonzalez (1985) , som använde den som en del av giriga approximationsalgoritmer för två problem i klustring, där målet är att dela upp en uppsättning punkter i k kluster. Ett av de två problemen som Gonzalez löser på detta sätt försöker minimera den maximala diametern för ett kluster, medan det andra, känt som det metriska k - centrumproblemet, försöker minimera den maximala radien, avståndet från en vald central punkt i en kluster till den längsta punkten från det i samma kluster. Till exempel k -centerproblemet användas för att modellera placeringen av brandstationer i en stad, för att säkerställa att varje adress i staden kan nås snabbt av en brandbil. För båda klustringsproblemen väljer Gonzalez en uppsättning k klustercentra genom att välja de första k punkterna i en längst-första genomgång och skapar sedan kluster genom att tilldela varje ingångspunkt till närmaste klustercentrum. Om r är avståndet från uppsättningen av k valda centra till nästa punkt vid position k + 1 i genomgången, så är med denna klustring varje punkt inom avståndet r från sitt centrum och varje kluster har en diameter på högst 2 r . Emellertid är delmängden av k centra tillsammans med nästa punkt alla på avstånd minst r från varandra, och varje k -klustring skulle placera två av dessa punkter i ett enda kluster, med en av dem på minst r / 2 från dess centrum och med diameter minst r . Således ger Gonzalez heuristik ett approximationsförhållande på 2 för båda klustringsproblemen.

Gonzalez heuristik återupptäcktes oberoende av det metriska k -centrumproblemet av Dyer & Frieze (1985), som tillämpade den mer generellt på viktade k -centerproblem. En annan artikel om k -centerproblemet från samma tid, Hochbaum & Shmoys (1985), uppnår samma approximationsförhållande på 2, men dess tekniker är olika. Icke desto mindre tillskrivs Gonzalez heuristik och namnet "farthest-first traversal", ofta felaktigt till Hochbaum och Shmoys. För både klustringsproblemet med min-max diameter och det metriska k -centrumproblemet är dessa approximationer optimala: förekomsten av en polynom-tidsheuristik med varje konstant approximationsförhållande mindre än 2 skulle innebära att P = NP .

Förutom för klustring kan den längst-första traverseringen också användas i en annan typ av anläggningslokaliseringsproblem, max-min anläggningsspridningsproblemet, där målet är att välja placeringen av k olika anläggningar så att de är så långt . från varandra som möjligt. Mer exakt är målet i detta problem att välja k punkter från ett givet metriskt utrymme eller en given uppsättning kandidatpunkter, på ett sådant sätt att det minsta parvisa avståndet mellan de valda punkterna maximeras. Återigen, detta kan approximeras genom att välja de första k punkterna i en längst-först genomgång. Om r anger avståndet för den k: te punkten från alla tidigare punkter, så är varje punkt i det metriska utrymmet eller kandidatmängden inom avståndet r från de första k − 1 punkterna. Enligt duvhålsprincipen måste två punkter av den optimala lösningen (vad det än är) båda vara inom avstånd r från samma punkt bland dessa första k − 1 valda punkter, och (genom triangelolikheten ) inom avståndet 2 r från varandra . Därför är den heuristiska lösningen som ges av längst-först genomgång inom en faktor två av optimal.

Andra tillämpningar av den längst borta först genomgången inkluderar färgkvantisering (klustring av färgerna i en bild till en mindre uppsättning representativa färger), progressiv skanning av bilder (välja en ordning för att visa pixlarna i en bild så att prefixen i beställningen ger bra versioner med lägre upplösning av hela bilden istället för att fylla i bilden uppifrån och ned), punktval i den probabilistiska färdplansmetoden för rörelseplanering , förenkling av punktmoln , generering av masker för halvtonsbilder , hierarkisk klustring , hitta likheterna mellan polygoner maskor av liknande ytor, val av olika och värdefulla observationsmål för utforskning av undervattensrobotar, feldetektering i sensornätverk , modellering av fylogenetisk mångfald , matchning av fordon i en heterogen flotta till kundernas leveransförfrågningar, enhetlig fördelning av geodetiska observatorier på jordens yta eller andra typer av sensornätverk, generering av virtuella punktljus i den omedelbara renderingsmetoden för datorgrafik och geometriska datastrukturer för sökning av data .

Algoritmer

Girig exakt algoritm

Den längst borta första genomgången av en ändlig punktuppsättning kan beräknas med en girig algoritm som upprätthåller avståndet för varje punkt från de tidigare valda punkterna, genom att utföra följande steg:

• Initiera sekvensen av valda punkter till den tomma sekvensen, och avstånden för varje punkt till de valda punkterna till oändlighet.
• Även om inte alla punkter har valts, upprepa följande steg:
  • Skanna listan över ännu inte valda punkter för att hitta en punkt p som har det maximala avståndet från de valda punkterna.
  • Ta bort p från de ännu inte valda punkterna och lägg till det i slutet av sekvensen av valda punkter.
  • För varje återstående ännu inte vald punkt q , ersätt avståndet som lagrats för q med minimum av dess gamla värde och avståndet från p till q .

För en uppsättning av n punkter tar denna algoritm O ( n ² ) steg och O ( n ² ) avståndsberäkningar.

Uppskattningar

En snabbare approximationsalgoritm , given av Har-Peled & Mendel (2006), gäller för vilken delmängd som helst av punkter i ett metriskt utrymme med avgränsad dubbleringsdimension , en klass av utrymmen som inkluderar de euklidiska utrymmena med avgränsad dimension. Deras algoritm hittar en sekvens av punkter där varje på varandra följande punkt har ett avstånd inom en 1 − ε faktor av det längsta avståndet från den tidigare valda punkten, där ε kan väljas att vara vilket positivt tal som helst. Det tar tid $O(n\log n)$ .

Resultaten för avgränsad dubbleringsdimension gäller inte högdimensionella euklidiska rum, eftersom den konstanta faktorn i den stora O-notationen för dessa algoritmer beror på dimensionen. Istället har en annan approximationsmetod baserad på Johnson–Lindenstrauss lemma och lokalitetskänslig hashing körtid ${\displaystyle O(\varepsilon ^{-2}n^{1+1/(1+\varepsilon )^{2}+o(1)}).} För mått som definieras av kortaste vägar på vägda oriktade$ grafer , en randomiserad inkrementell konstruktion baserad på Dijkstras algoritm uppnår tid $O(\varepsilon ^{-1}m\log n\log {\tfrac {n}{\varepsilon }})$ , där n och m är antalet hörn respektive kanter på inmatningsgrafen.

Inkrementell Voronoi-insättning

För att välja punkter från ett kontinuerligt utrymme som det euklidiska planet , snarare än från en ändlig uppsättning kandidatpunkter, kommer dessa metoder inte att fungera direkt, eftersom det skulle finnas ett oändligt antal avstånd att upprätthålla. Istället bör varje ny punkt väljas som mitten av den största tomma cirkeln som definieras av den tidigare valda punktuppsättningen. Detta centrum kommer alltid att ligga på en vertex av Voronoi-diagrammet för de redan valda punkterna, eller vid en punkt där en kant av Voronoi-diagrammet korsar domängränsen. I denna formulering har metoden för att konstruera längst-först-traverser också kallats inkrementell Voronoi-insättning . Det liknar Delaunay-förfining för generering av finita elementnät , men skiljer sig i valet av vilken Voronoi-vertex som ska infogas vid varje steg.

Se även

• Lloyds algoritm , en annan metod för att generera jämnt fördelade punkter i geometriska utrymmen