Det minsta cirkelproblemet

Problemet med den minsta cirkeln eller problemet med den minsta täckande cirkeln är problemet med att beräkna den minsta cirkeln som innehåller alla givna punkter från en uppsättning på det euklidiska planet . Motsvarande problem i n -dimensionell rymd , det minst gränsande sfärproblemet , beräknar den minsta hypersfären som innehåller alla punkter i en given uppsättning [1] . Problemet med den minsta cirkeln ställdes först av den engelske matematikern James Joseph Sylvester 1857 [2] .

Det minsta cirkelproblemet är ett exempel på ett objektplaceringsproblem ( 1-centerproblemet ), där platsen för en ny organisation måste väljas för att betjäna en given uppsättning kunder samtidigt som man minimerar det maximala avstånd som en kund måste resa för att nå organisationen [3] . Både problemet med den minsta cirkeln i planet och problemet med den minsta gränsande hypersfären i högre dimensioner är lösbara i linjär tid .

Beskrivning

De flesta geometriska tillvägagångssätt till problemet tittar på punkter som ligger på gränsen till en minimal cirkel och är baserade på följande enkla fakta:

Lösning i linjär tid

Som visat av Nimrod Megiddo [4] kan den minsta begränsningscirkeln hittas i linjär tid, och detsamma gäller för den minsta gränssfären i högre euklidiska rum.

Emo Welzl [5] föreslog en enkel randomiserad algoritm för cirkeltäckningsproblemet med en genomsnittlig körtid på , baserad på Raymond Seidels linjära programmeringsalgoritm . Algoritmen är rekursiv och tar två uppsättningar av punkter S och Q som argument . Algoritmen beräknar den minsta cirkeln som begränsar föreningen av mängderna S och Q om någon punkt i mängden Q är en gränspunkt för en möjlig gränscirkel. Det ursprungliga minsta gränsande cirkelproblemet kan lösas genom att börja med S lika med hela uppsättningen punkter och med Q lika med den tomma mängden . När algoritmen anropar sig själv rekursivt, ökar den mängden Q tills den innehåller alla gränspunkter.

Algoritmen bearbetar punkterna i mängden S i slumpmässig ordning, med användning av mängden P av bearbetade punkter och minimicirkeln som begränsar föreningen av P och Q . Vid varje steg kontrollerar algoritmen om den behandlade punkten r tillhör denna cirkel. Om inte, ersätter algoritmen den gränsande cirkeln genom att rekursivt anropa algoritmen på uppsättningarna P och Q + r . Beroende på om cirkeln byts ut eller inte ingår r i mängden P . Bearbetningen av varje punkt består alltså i att kontrollera (i konstant tid) om punkten tillhör cirkeln och eventuellt rekursivt anropa algoritmen. Det kan visas att den i : te bearbetningspunkten har sannolikheten för ett rekursivt anrop, och därför är den totala tiden linjär.

Senare inkluderades det minsta cirkelproblemet i den allmänna klassen av LP-typproblem , som kan lösas med algoritmer liknande Welzl-algoritmen baserad på linjär programmering. Som en konsekvens av att tillhöra denna klass visades det att beroendet av den konstanta faktorn på dimensionen i tidsuppskattningen , som var faktoriell i Seidelmetoden, kan reduceras till subexponentiell, men tidsuppskattningen förblir linjär i N [ 6] .

Andra algoritmer

Innan Megiddos resultat visade att det minsta cirkelproblemet kan lösas i linjär tid, dök det upp algoritmer med större komplexitet i litteraturen. Den naiva algoritmen löser problemet i O( n 4 ) tid genom att kontrollera cirklarna som ges av alla par och trillingar av punkter.

Viktade varianter av problemet

Den viktade versionen av problemet med minsta spänncirkel tar som ingångspunkter i det euklidiska rummet med en vikt tilldelad varje punkt. Målet med problemet är att hitta en enda punkt som minimerar det maximala viktade avståndet till vilken punkt som helst. Det ursprungliga problemet med att täcka med en cirkel kan betraktas som ett problem med samma vikter. Liksom i fallet med ett problem utan vikter, kan ett viktat problem lösas i linjär tid i vilket utrymme som helst med begränsad dimension, med ett tillvägagångssätt baserat på en bounded linjär programmeringsalgoritm, även om långsammare algoritmer ständigt finns i litteraturen [12] [ 16] [17] .

Se även

Anteckningar

  1. ↑ 1 2 Elzinga, Hearn, 1972 , sid. 96–104.
  2. ↑ Sylvester, 1857 , sid. 79.
  3. ↑ Francis, McGinnis, White, 1992 .
  4. ↑ Megiddo, 1983 , sid. 759–776.
  5. ↑ Welzl, 1991 , sid. 359–370.
  6. ↑ Matoušek, Sharir, Welzl, 1996 , sid. 498–516.
  7. ↑ Chakraborty, Chaudhuri, 1981 , sid. 164–166.
  8. ↑ Elzinga, Hearn, 1972 , sid. 379–394.
  9. ↑ Drezner och Shelah 1987 , sid. 255–261.
  10. ↑ Hearn, Vijay, Nickel, 1995 , sid. 236–237.
  11. ↑ Jacobsen, 1981 , sid. 144–148.
  12. ↑ 1 2 3 Hearn, Vijay, 1982 , sid. 777–795.
  13. ↑ Elzinga, Hearn, Randolph, 1976 , sid. 321–336.
  14. ↑ Lawson, 1965 , sid. 415–417.
  15. ↑ Shamos och Hoey 1975 , sid. 151–162.
  16. ↑ Megiddo, 1983 , sid. 498–504.
  17. ↑ Megiddo, Zemel, 1986 , sid. 358–368.

Litteratur

Länkar