\(\epsilon\)-nets and simplex range queries (Q1089803): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 02:10, 5 March 2024

scientific article
Language Label Description Also known as
English
\(\epsilon\)-nets and simplex range queries
scientific article

    Statements

    \(\epsilon\)-nets and simplex range queries (English)
    0 references
    0 references
    0 references
    1987
    0 references
    The main problem may be described as follows: given a set of n points in d-dimensional Euclidean space, find a data structure that uses linear storage such that the number of points in any query half space can be determined in sublinear time \(O(n^{\alpha})\). A data structure with \(\alpha =d(d-1)/(d(d-1)+1)+\gamma\) for any \(\gamma >0\) is exhibited. These bounds for \(\alpha\) are better than those previously published for all \(d\geq 2\) by \textit{A. Yao} and \textit{F. Yao} [A general approach to d- dimensional geometric queries. Proc. 17th Symp. Theory of Computing, 163- 169 (1985)]. Let X be a set and R be a set of subsets of X, which have a finite dimension in Vapnik-Chervonenkis sense [\textit{V. N. Vapnik} and \textit{A. Ya. Chervonenkis}: The theory of pattern recognition (Russian) (1974; Zbl 0284.68070)], A be a finite subset of X and \(0\leq \epsilon \leq 1\). A subset N of A is an \(\epsilon\)-net of A (for R) if N contains a point in each \(r\in R\) such that \(| A\cap r| /| A| >\epsilon\). The authors prove that for \(0<\epsilon\), \(\delta <1\), if N is a subset of A obtained by \(m\geq \max (4/\epsilon \log 2/\delta,8d/\epsilon \log 8d/\epsilon)\) random independent draws, then N is an \(\epsilon\)-net of A with probability at least 1-\(\delta\). Using this result, a partition tree structure that achieves the above query time is constructed.
    0 references
    simplex range queries
    0 references
    counting problem
    0 references
    partitioning point sets
    0 references
    data structure
    0 references
    query half space
    0 references
    sublinear time
    0 references
    partition tree structure
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references