Article

Free access

Epsilon-nets and simplex range queries

Authors:

E WelzlAuthors Info & Claims

SCG '86: Proceedings of the second annual symposium on Computational geometry

Pages 61 - 71

https://doi.org/10.1145/10515.10522

Published: 01 August 1986 Publication History

Abstract

We present a new technique for half-space and simplex range query using Ο(n) space and Ο(n^a) query time, where a < d(d-1)/d(d-1) + 1 + γ for all dimensions d ≥ 2 and γ > 0. These bounds are better than those previously published for all d ≥ 2. The technique uses random sampling to build a partition-tree structure. We introduce the concept of an ε-net for an abstract set of ranges to describe the desired result of this random sampling and give necessary and sufficient conditions that a random sample is an ε-net with high probability. We illustrate the application of these ideas to other range query problems.

References

[1]

A. Blumer, A. Ehrenfeucht, D. Haussler, M. Warmuth, "Classifying learnable geometric concepts with Lhe Vapnik-Chervonenkis dimension," Proc. 18th Syrup. on Theory of Computation, (1986) to appear.

Digital Library

[2]

B. Chazelle, L. Guibas and D.T. Lee, "The power of geometric duality," Proc. 24th Syrup. on Foundations of Comp Sci, 1983, 217-225.

[3]

K. Clarkson, "A probabilistic algorithm for the post office problem," Proc. 1 ?th Syrup, an Theory of Computation, (1985) 175-185.

Digital Library

[4]

R. Cole, "Partitioning point sets in 4 dimensions," Prac. Colloq. on Autom. o Lang. and Progr., (1985), 111-119, Lecture Notes in Comput. Set. 194, Springer, Berlin.

Digital Library

[5]

D. Dobkin and H. Edelsbrunner, "Organizing points in two and three dimensions," Tech. Rep. F130, Technische Universitat Qraz, 1984. .

[6]

D. Dobkin, H. Edelsbrunner and F. Yao, "A 3-space partition and its applications'', manuscript.

[7]

R.M. Dudley, "Central limit theorems for empirical measures," Ann. Prob., 8 (6)(1978)899-929.

[8]

H. Edelsbrunner and E. Welzl, "Halfplane range search in linear space and O(n~'~95) query time,"/nf. Proc. Let., to appear,

Digital Library

[9]

H. Edelsbrunner and F. Huber, "Dissecting sets of points in two and three dimensions," Tech. Rep. F138, Technische Universitat Graz, 1984. {EDL 85} H. Edelsbrunner, Open problem in Bu/l. ZA TCS 26 (1985).

[10]

Branko Gruenbaum, Convex Palytopes, lnterscience (1967)

[11]

V.N. Vapnik and A. YA. Chervonenkis, "On the uniform convergence of relative frequencies of events to their probabilities," Th. Prob. and its Appl. 16 (2) (1971) 264-280.

[12]

R.S. Wenocur and R.M. Dudley, "Some special Vapnik-Chervonenkis classes," Discrete Math., 31 (1891) 313- 318.

[13]

D. Willard, "Polygon retrieval," $/~ J. Cam.put., 11 (1982) 149-165.

[14]

F. Yao, '~A 3-space partition and its applications," Proc. 15th Syrup. on Theory a/Computation, (1983) 258-263.

Digital Library

[15]

A. Yao and F. Yao, "A general approach to d-dimensional geometric queries," Prac. 1 ?th Syrnp. on Theory of Computation, (1985) 163-169.

Digital Library

Cited By

Fung KZhang QLu CWan JWilli TFoerster JDastani MSichman JAlechina NDignum V(2024)Analysing the Sample Complexity of Opponent ShapingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662914(623-631)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662914
Gan JUmboh SWang HWirth AZhang Z(2024)Optimal Dynamic Parameterized Subset SamplingProceedings of the ACM on Management of Data10.1145/36958272:5(1-26)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695827
Shahbazi NLin YAsudeh AJagadish H(2023)Representation Bias in Data: A Survey on Identification and Resolution TechniquesACM Computing Surveys10.1145/358843355:13s(1-39)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3588433
Show More Cited By

Index Terms

Recommendations

ź-nets and simplex range queries

We demonstrate the existence of data structures for half-space and simplex range queries on finite point sets ind-dimensional space,d 2, with linear storage andO(n ) query time, $$\alpha = \frac{{d(d - 1)}}{{d(d - 1) + 1}} + \gamma for all \gamma > 0$$ ...
Tight lower bounds for the size of epsilon-nets
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an ε-net of size O(1/ε log 1/ε). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-...
Range queries on uncertain data

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '86: Proceedings of the second annual symposium on Computational geometry

August 1986

322 pages

ISBN:0897911946

DOI:10.1145/10515

Chairman:
Alok Aggarwal

Copyright © 1986 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

CG86

Sponsor:

CG86: The 2nd Annual ACM SIGACT/SIGGRAPH Symposium on Computational Geometry

June 2 - 4, 1986

New York, Yorktown Heights, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
1,891
Total Downloads

Downloads (Last 12 months)269
Downloads (Last 6 weeks)33

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fung KZhang QLu CWan JWilli TFoerster JDastani MSichman JAlechina NDignum V(2024)Analysing the Sample Complexity of Opponent ShapingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662914(623-631)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3662914
Gan JUmboh SWang HWirth AZhang Z(2024)Optimal Dynamic Parameterized Subset SamplingProceedings of the ACM on Management of Data10.1145/36958272:5(1-26)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695827
Shahbazi NLin YAsudeh AJagadish H(2023)Representation Bias in Data: A Survey on Identification and Resolution TechniquesACM Computing Surveys10.1145/358843355:13s(1-39)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3588433
Afshani PCheng P(2023)Lower Bounds for Semialgebraic Range Searching and Stabbing ProblemsJournal of the ACM10.1145/357857470:2(1-26)Online publication date: 18-Apr-2023
https://dl.acm.org/doi/10.1145/3578574
Aarts SShmoys D(2023)Hitting Sets when the Shallow Cell Complexity is SmallApproximation and Online Algorithms10.1007/978-3-031-49815-2_12(160-174)Online publication date: 22-Dec-2023
https://doi.org/10.1007/978-3-031-49815-2_12
Marecek JMaroulis SKalogeraki VGunopulos D(2022)Low-Rank Methods in Event Detection With Subsampled Point-to-Subspace Proximity TestsIEEE Access10.1109/ACCESS.2022.315220610(32525-32536)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3152206
Blum JFunke SStorandt S(2021)Sublinear search spaces for shortest path planning in grid and road networksJournal of Combinatorial Optimization10.1007/s10878-021-00777-3Online publication date: 29-Jul-2021
https://doi.org/10.1007/s10878-021-00777-3
Grubbs PLacharite MMinaud BPaterson K(2019)Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks2019 IEEE Symposium on Security and Privacy (SP)10.1109/SP.2019.00030(1067-1083)Online publication date: May-2019
https://doi.org/10.1109/SP.2019.00030
Hayashi KYoshida Y(2019)Testing Proximity to Subspaces: Approximate $$\ell _\infty $$ ℓ ∞ Minimization in Constant TimeAlgorithmica10.1007/s00453-019-00642-0Online publication date: 25-Oct-2019
https://doi.org/10.1007/s00453-019-00642-0
Feldman D(2019)Core-Sets: Updated SurveySampling Techniques for Supervised or Unsupervised Tasks10.1007/978-3-030-29349-9_2(23-44)Online publication date: 27-Oct-2019
https://doi.org/10.1007/978-3-030-29349-9_2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents