Weak -nets have basis of size o(1/ log (1/)) in any dimension

Nabil Mustafa; Saurabh Ray

doi:10.1145/1247069.1247113

Weak -nets have basis of size o(1/ log (1/)) in any dimension

Nabil Mustafa, Saurabh Ray

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a set P of n points in R^d and > 0, we consider the problemof constructing weak -nets for P.We show the following: pick a random sample Q of size O(1/ log (1/)) from P. Then, with constant probability, a weak -net of P can be constructed from only the points of Q. This shows that weak -nets in R^d can be computed from a subset of P of size O(1/ log(1/)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/. However, our final weak -nets still have a large size (with the dimension appearing in the exponent of 1/).

Original language	English (US)
Title of host publication	Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
Pages	239-244
Number of pages	6
DOIs	https://doi.org/10.1145/1247069.1247113
State	Published - 2007
Event	23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of Duration: Jun 6 2007 → Jun 8 2007

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	23rd Annual Symposium on Computational Geometry, SCG'07
Country/Territory	Korea, Republic of
City	Gyeongju
Period	6/6/07 → 6/8/07

Keywords

Combinatorial geometry
Discrete geometry
Hitting convex sets
Weak epsilon nets

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/1247069.1247113

Cite this

Mustafa, N & Ray, S 2007, Weak -nets have basis of size o(1/ log (1/)) in any dimension. in Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07. Proceedings of the Annual Symposium on Computational Geometry, pp. 239-244, 23rd Annual Symposium on Computational Geometry, SCG'07, Gyeongju, Korea, Republic of, 6/6/07. https://doi.org/10.1145/1247069.1247113

@inproceedings{5e1fc257646b4d66b4f60c3ba7099b05,

title = "Weak -nets have basis of size o(1/ log (1/)) in any dimension",

abstract = "Given a set P of n points in Rd and > 0, we consider the problemof constructing weak -nets for P.We show the following: pick a random sample Q of size O(1/ log (1/)) from P. Then, with constant probability, a weak -net of P can be constructed from only the points of Q. This shows that weak -nets in Rd can be computed from a subset of P of size O(1/ log(1/)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/. However, our final weak -nets still have a large size (with the dimension appearing in the exponent of 1/).",

keywords = "Combinatorial geometry, Discrete geometry, Hitting convex sets, Weak epsilon nets",

author = "Nabil Mustafa and Saurabh Ray",

year = "2007",

doi = "10.1145/1247069.1247113",

language = "English (US)",

isbn = "1595937056",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "239--244",

booktitle = "Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07",

note = "23rd Annual Symposium on Computational Geometry, SCG'07 ; Conference date: 06-06-2007 Through 08-06-2007",

}

TY - GEN

T1 - Weak -nets have basis of size o(1/ log (1/)) in any dimension

AU - Mustafa, Nabil

AU - Ray, Saurabh

PY - 2007

Y1 - 2007

N2 - Given a set P of n points in Rd and > 0, we consider the problemof constructing weak -nets for P.We show the following: pick a random sample Q of size O(1/ log (1/)) from P. Then, with constant probability, a weak -net of P can be constructed from only the points of Q. This shows that weak -nets in Rd can be computed from a subset of P of size O(1/ log(1/)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/. However, our final weak -nets still have a large size (with the dimension appearing in the exponent of 1/).

AB - Given a set P of n points in Rd and > 0, we consider the problemof constructing weak -nets for P.We show the following: pick a random sample Q of size O(1/ log (1/)) from P. Then, with constant probability, a weak -net of P can be constructed from only the points of Q. This shows that weak -nets in Rd can be computed from a subset of P of size O(1/ log(1/)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/. However, our final weak -nets still have a large size (with the dimension appearing in the exponent of 1/).

KW - Combinatorial geometry

KW - Discrete geometry

KW - Hitting convex sets

KW - Weak epsilon nets

UR - http://www.scopus.com/inward/record.url?scp=35348925348&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35348925348&partnerID=8YFLogxK

U2 - 10.1145/1247069.1247113

DO - 10.1145/1247069.1247113

M3 - Conference contribution

AN - SCOPUS:35348925348

SN - 1595937056

SN - 9781595937056

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 239

EP - 244

BT - Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07

T2 - 23rd Annual Symposium on Computational Geometry, SCG'07

Y2 - 6 June 2007 through 8 June 2007

ER -

Weak -nets have basis of size o(1/ log (1/)) in any dimension

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this