Pevný rádius u sousedů - Fixed-radius near neighbors

v výpočetní geometrie, problém s pevným poloměrem poblíž souseda je varianta hledání nejbližšího souseda problém. V problému s blízkým sousedem s pevným poloměrem je jeden zadán jako vstup do sady bodů d-dimenzionální Euklidovský prostor a pevnou vzdálenost Δ. Jeden musí navrhnout datovou strukturu, která vzhledem k bodu dotazu q, efektivně hlásí body datové struktury, které jsou ve vzdálenosti Δ od q. Problém byl dlouho studován; Bentley (1975) uvádí dokument Levinthal z roku 1966, který používá tuto techniku ​​jako součást systému pro vizualizaci molekulárních struktur a má mnoho dalších aplikací.[1]

Řešení zaokrouhlováním a hašováním

Jednou z metod řešení problému je zaokrouhlování bodů na celočíselná mřížka, zmenšen tak, aby vzdálenost mezi body mřížky byla požadovaná vzdálenost Δ. A hash tabulka lze pro každý vstupní bod použít k vyhledání dalších vstupů, které jsou mapovány na blízké body mřížky, které lze poté otestovat, zda jsou jejich nezaokrouhlené polohy ve vzdálenosti Δ. Počet párů bodů testovaných tímto postupem a doba postupu jsou lineární v kombinované velikosti vstupu a výstupu, když je kóta pevnou konstantou. Nicméně konstanta proporcionality v lineárním časovém ohraničení roste exponenciálně jako funkce dimenze.[2] Pomocí této metody je možné sestrojit indiferenční grafy a jednotkové diskové grafy z geometrických dat v lineárním čase.

Další řešení

Moderní paralelní metody pro GPU jsou schopné efektivně vypočítat všechny páry NNS s pevným poloměrem. U konečných domén je to metoda Green [3] ukazuje, že problém lze vyřešit tříděním na jednotné mřížce, nalezením všech sousedů všech částic v čase O (kn), kde k je úměrné průměrnému počtu sousedů. Hoetzlein [4] to dále vylepšuje na moderním hardwaru počítáním třídění a atomových operací.

Aplikace

Problém blízkého souseda s pevným poloměrem vzniká v kontinuálních Lagrangeových simulacích (jako je hydrodynamika vyhlazených částic), výpočetní geometrii a problémech mračna bodů (povrchové rekonstrukce).

Viz také

Reference

  1. ^ Bentley, Jon Louis (1975), Přehled technik pro hledání blízkých sousedů s pevným poloměrem (PDF), Technická zpráva SLAC-186 a STAN-CS-75-513, Stanford Linear Accelerator Center.
  2. ^ Bentley, Jon L.; Stanat, Donald F .; Williams, E. Hollins, Jr. (1977), „Složitost hledání pevného poloměru u sousedů“, Dopisy o zpracování informací, 6 (6): 209–212, doi:10.1016/0020-0190(77)90070-9, PAN  0489084.
  3. ^ Green, Simon (2012), CUDA částice (PDF)
  4. ^ Hoetzlein, Rama (2014), „Nejbližší sousedé s rychlým pevným poloměrem: Interaktivní tekutiny s miliony částic“ (PDF), Konference o technologii GPU