Hlášení dosahu - Range reporting - Wikipedia

v výpočetní geometrie a databáze teorie, a hlášení rozsahu dotaz požádá o seznam bodů, které odpovídají dotazu. Dotaz je často specifikován geometrickým tvarem, který obsahuje všechny body, které by se měly shodovat, a nazývá se rozsah. Hlášení rozsahu je zvláštní případ vyhledávání rozsahu, ve kterém mohou dotazy vracet další druhy souhrnných informací o bodech v rozsahu.

Dotazy na hlášení rozsahu se často zpracovávají sestavením a datová struktura ze sbírky bodů, které mohou efektivně odpovídat na dotazy. Protože nejhorší velikost výstupu pro dotaz na hlášení rozsahu, měřená jako funkce velikosti datové sady n, může být n sama o sobě byla zkoumána velká část výzkumu datových struktur pro hlášení rozsahu algoritmy citlivé na výstup, kde je čas dotazu analyzován z hlediska obou n a počet hlášených bodů (často označován k).

Například pro jednorozměrná (číselná) data s rozsahy dotazů, které jsou intervaly, dotazy na hlášení rozsahu lze zpracovat uložením dat do seřazeného pole. S touto strukturou lze použít binární vyhledávání najít bod nejblíže začátku intervalu dotazu, a poté skenovat pole od tohoto bodu dopředu a zobrazit všechny body v intervalu. Ukládání této datové struktury využívá Ó(n) (lineární) prostor a zpracovává dotazy v čase Ó(log n + k) na dotaz.

Reference

• Agarwal, P. K.; Erickson, J. (1999), „Hledání geometrického rozsahu a jeho příbuzní“ (PDF), v Chazelle, Bernard; Goodman, Jacobe; Pollack, Richard (eds.), Pokroky v diskrétní a výpočetní geometrii: sborník společných letních výzkumných konferencí AMS-IMS-SIAM z roku 1996, Diskrétní a výpočetní geometrie - o deset let později, 14. – 18. Července 1996, Mount Holyoke College, Současná matematika, 223, American Mathematical Society Press, s. 1–56.