Problem med geometriskt set omslag

Problemet med geometriskt uppsättningsskydd är det speciella fallet med uppsättningsskyddsproblemet i geometriska inställningar. Ingången är ett områdesutrymme $\Sigma =(X,{\mathcal {R}})$ där $X$ är ett universum av punkter i $\ mathbb {R} ^{d}$ och ${\mathcal {R}}$ är en familj av delmängder av $X$ som kallas intervall , definierade av skärningspunkten mellan $X$ och geometrisk former som skivor och axelparallella rektanglar. Målet är att välja en delmängd av minsta storlek ${\mathcal {C}}\subseteq {\mathcal {R}}$ av intervall så att varje punkt i universum $X$ täcks av något intervall i ${\mathcal {C}}$ .

Givet samma områdesutrymme $\Sigma$ , är ett närbesläktat problem det geometriska träffmängdsproblemet , där målet är att välja en delmängd $H\subseteq X$ av punkter så att varje intervall av ${\mathcal {R}}$ har icke-tom skärningspunkt med $H$ , dvs träffas av $H$ .

I det endimensionella fallet, där $X$ innehåller punkter på den reella linjen och ${\mathcal {R}}$ definieras av intervaller, kan både det geometriska setets täckning och träffuppsättningsproblemen lösas i polynomtid med en enkel girig algoritm . Men i högre dimensioner är de kända för att vara NP-kompletta även för enkla former, dvs när ${\mathcal {R}}$ induceras av enhetsskivor eller enhetskvadrater. Problemet med diskreta enhetsskivor är en geometrisk version av det generella setlocket som är NP-hårt .

Många approximationsalgoritmer har utarbetats för dessa problem. På grund av den geometriska karaktären kan approximationsförhållandena för dessa problem vara mycket bättre än de generella problem med uppsättning täckning/slagsats. Dessutom kan dessa ungefärliga lösningar till och med beräknas i nästan linjär tid.

Approximationsalgoritmer

Den giriga algoritmen för det allmänna uppsättningsomslagsproblemet ger $O(\log n)$ approximation, där $n=\max\{|X|,|{\mathcal {R}}|\}$ . Denna approximation är känd för att vara snäv upp till konstant faktor. Men i geometriska inställningar kan bättre approximationer erhållas. Med hjälp av en multiplikativ viktalgoritm visade Brönnimann och Goodrich att en $O(\log {\mathsf {OPT}})$ -ungefärlig uppsättning täckning/träffuppsättning för ett avståndsutrymme ${\ displaystyle \Sigma }$ med konstant VC-dimension kan beräknas i polynomtid, där $\displaystyle {\mathsf {OPT}}\leq n}$ anger storleken på den optimala lösningen. Approximationsförhållandet kan förbättras ytterligare till $O(\log \log {\mathsf {OPT}})$ eller $O(1)$ när ${\mathcal {R}}$ induceras av axelparallella rektanglar eller skivor i $\mathbb {R} ^{2}$ .

Algoritmer för nästan linjär tid

Baserat på den iterativa omviktningstekniken av Clarkson och Brönnimann och Goodrich, gav Agarwal och Pan algoritmer som beräknar en ungefärlig uppsättning täckning/träffuppsättning av ett geometriskt avståndsutrymme i ${\ displaystyle O(n~\mathrm {polylog} (n))}$ tid. Till exempel, deras algoritmer beräknar en $O(\log \log {\mathsf {OPT}})$ -ungefärlig träff satt i $O(n\log ^{3}n\log \log \log {\mathsf {OPT}})$ tid för avståndsutrymmen inducerade av 2D-axelparallella rektanglar; och den beräknar en $O(1)$ -ungefärlig uppsättning täckning i $O(n\log ^{4}n)$ tid för avståndsutrymmen inducerade av 2D-skivor.

Se även