Beta kostra - Beta skeleton

Kruhová kostra 1,1 (těžké tmavé hrany) a 0,9 kostra (světlé přerušované modré hrany) sady 100 náhodných bodů ve čtverci.

v výpočetní geometrie a teorie geometrických grafů, a β-kostra nebo kostra beta je neorientovaný graf definované ze sady bodů v Euklidovské letadlo. Dva body p a q jsou spojeny hranou, kdykoli jsou všechny úhly prq jsou ostřejší než prahová hodnota určená z číselného parametruβ.

Kruhová definice

Prázdné oblasti R_pq definování kružnice β-kostra. Vlevo, odjet: β <1. Střed: β = 1. Správně: β > 1.

Nechat β být pozitivní reálné číslo a vypočítat úhel θ pomocí vzorců

${ displaystyle theta = { begin {cases} sin ^ {- 1} { frac {1} { beta}}, a { text {if}} beta geq 1 pi - sin ^ {- 1} { beta}, & { text {if}} beta leq 1 end {cases}}}$

Za jakékoli dva body p a q v letadle, ať R_pq být množina bodů, pro které úhel prq je větší nežθ. Pak R_pq má podobu spojení dvou otevřených disků o průměru βd(p,q) pro β ≥ 1 a θ ≤ π / 2 a má podobu průniku dvou otevřených disků s průměrem d(p,q)/β pro β ≤ 1 a θ ≥ π / 2. Když β = 1 mají dva vzorce stejnou hodnotu θ = π / 2 a R_pq má formu jediného otevřeného disku s pq jako jeho průměr.

The β- kostra a diskrétní sada S bodů v rovině je neorientovaný graf který spojuje dva body p a q s hranou pq kdykoli R_pq neobsahuje žádné body z S. Toto je β-skeleton je prázdný graf oblasti definovaný regiony R_pq.^[1] Když S obsahuje bod r pro jaký úhel prq je větší než θ, pak pq není okrajem β-kostra; the β-skelet se skládá z těchto párů pq pro které žádný takový bod neexistuje r existuje.

Luneová definice

Někteří autoři používají alternativní definici, ve které jsou prázdné oblasti R_pq pro β > 1 nejsou svazky dvou disků, ale spíše čočky (častěji se v této souvislosti nazývá „luny "), průniky dvou shodných disků s průměrem βd(pq), jako je ten úsečka pq leží na poloměru obou disků a tak, že body p a q oba leží na hranici křižovatky. Stejně jako u kruhu β-skeleton, založený na luně β- kostra má hranu pq kdykoli region R_pq je prázdný od ostatních vstupních bodů. Pro tuto alternativní definici je graf relativního sousedství je speciální případ a β- kostra s β = 2. Obě definice se shodují pro β ≤ 1 a pro větší hodnoty β kruhová kostra je a podgraf kostry založené na luně.

Jeden důležitý rozdíl mezi kruhovým a lune-based β-skeletons je, že pro libovolnou množinu bodů, která neleží na jednom řádku, vždy existuje dostatečně velká hodnota β takové, že kruhové β- kostra je prázdný graf. Naproti tomu, pokud dvojice bodů p a q má vlastnost, která pro všechny ostatní body r, jeden ze dvou úhlů pqr a qpr je tupý, pak založený na luně β-skeleton bude obsahovat hranu pq bez ohledu na to, jak velký β je.

Dějiny

β- kostry byly nejprve definovány Kirkpatrick & Radke (1985) jako scale-invariant variace alfa tvary z Edelsbrunner, Kirkpatrick & Seidel (1983). Název, "β-skeleton, odráží skutečnost, že v jistém smyslu β-skeleton popisuje tvar množiny bodů stejným způsobem jako a topologická kostra popisuje tvar dvojrozměrné oblasti. Několik zevšeobecnění β-zvažuje se také kostra grafů definovaných jinými prázdnými oblastmi.^[1][2]

Vlastnosti

Li β se průběžně mění od 0 do ∞, podle kruhu βkostry tvoří posloupnost grafů sahajících od kompletní graf do prázdný graf. Zvláštní případ β = 1 vede k Gabriel graf, o kterém je známo, že obsahuje Euklidovský minimální kostra; proto β-skeleton také kdykoli obsahuje Gabrielův graf a minimální kostru β ≤ 1.

Pro každou konstantu β, a fraktální konstrukce připomínající zploštělou verzi Sněhová vločka Koch lze použít k definování posloupnosti množin bodů, jejichž β- kostry jsou cesty libovolně velké délky v jednotkovém čtverci. Proto, na rozdíl od úzce souvisejících Delaunayova triangulace, β- kostry jsou neomezené napínací faktor a nejsou geometrické klíče.^[3]

Algoritmy

A naivní algoritmus který testuje každou trojici p, q, a r pro členství v r v oblasti R_pq může postavit β- kostra libovolné sady n body v čase O (n³).

Když β ≥ 1, β-skeleton (s oběma definicemi) je podgrafem Gabrielova grafu, který je podgrafem Delaunayova triangulace. Li pq je hrana Delaunayovy triangulace, která není hranou β- kostra, pak bod r který tvoří velký úhel prq lze najít jako jeden z nejvýše dvou bodů tvořících trojúhelník s p a q v Delaunayově triangulaci. Proto pro tyto hodnoty β, kruhový β- kostra pro sadu n body lze postavit v čase O (n logn) výpočtem Delaunayovy triangulace a použitím tohoto testu k filtrování jeho okrajů.^[2]

Pro β <1, jiný algoritmus Hurtado, Liotta & Meijer (2003) umožňuje stavbu β-skelet v čase O (n²). Žádný lepší časově nejhorší případ není možný, protože pro jakoukoli pevnou hodnotu β menší než jedna, existují množiny bodů v obecné poloze (malé odchylky a pravidelný mnohoúhelník ) pro které β-skeleton je a hustý graf s kvadratickým počtem hran. Ve stejném kvadratickém časovém ohraničení celý β-spectrum (sled kruhů βkostry tvořené varováním β) lze také vypočítat.

Aplikace

Kruhový β- kostra může být použita v analýza obrazu rekonstruovat tvar dvourozměrného objektu vzhledem k sadě vzorových bodů na hranici objektu (výpočetní forma spojit tečky skládačka, kde posloupnost, ve které mají být body spojeny, musí být odvozena pomocí algoritmu, spíše než uvedena jako součást skládačky). I když to obecně vyžaduje výběr hodnoty parametru β, je možné tuto volbu dokázat β = 1,7 správně rekonstruuje celou hranici libovolného hladkého povrchu a nebude generovat žádné hrany, které k této hranici nepatří, pokud jsou vzorky generovány dostatečně hustě vzhledem k místnímu zakřivení povrchu.^[4] Při experimentálním testování však nižší hodnota β = 1,2, bylo účinnější pro rekonstrukci pouličních map ze sad bodů označujících středové čáry ulic v a geografický informační systém.^[5] Pro zobecnění β- skeletová technika k rekonstrukci povrchů ve třech rozměrech, viz Hiyoshi (2007).

Kruhový β- kostry byly použity k nalezení podgrafů triangulace minimální hmotnosti množiny bodů: pro dostatečně velké hodnoty β, každý β- lze zaručit, že hrana kostry patří do triangulace s minimální hmotností. Pokud takto nalezené hrany tvoří a připojený graf na všech vstupních bodech pak zbývající trojúhelníkové hrany minimální hmotnosti najdete v polynomiální čas podle dynamické programování. Obecně je problém triangulace s minimální hmotností NP-tvrdý a podmnožina jeho hran nalezených tímto způsobem nemusí být spojena.^[6]

β- kostry byly také použity v strojové učení řešit geometrické klasifikace problémy^[7] a v bezdrátové sítě ad hoc jako mechanismus pro řízení složitosti komunikace výběrem podmnožiny párů bezdrátových stanic, které mohou spolu komunikovat.^[8]

Poznámky

Reference