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

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Density and dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3687757 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Central limit theorems for empirical measures / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3772828 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructing Belts in Two-Dimensional Arrangements with Applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Halfplanar range search in linear space and \(O(n^{0.695})\) query time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5547252 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the density of families of sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4770512 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some special Vapnik-Chervonenkis classes / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polygon Retrieval / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3278735 / rank
 
Normal rank

Revision as of 19:02, 17 June 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