LIPIcs.SoCG.2016.59.pdf
- Filesize: 0.51 MB
- 13 pages
Document
Weak 1/r-Nets for Moving Points
Authors
-
Part of:
Volume:
32nd International Symposium on Computational Geometry (SoCG 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-10
Cite As Get BibTex
Alexandre Rok and Shakhar Smorodinsky. Weak 1/r-Nets for Moving Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.59
Abstract
In this paper, we extend the weak 1/r-net theorem to a kinetic setting where the underlying set of points is moving polynomially with bounded description complexity. We establish that one can find a kinetic analog N of a weak 1/r-net of cardinality O(r^(d(d+1)/2)log^d r) whose points are moving with coordinates that are rational functions with bounded description complexity. Moreover, each member of N has one polynomial coordinate.
Subject Classification
Keywords
- Hypergraphs
- Weak epsilon-net
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
N. Alon, I. Bárány, Z. Füredi, and D.J. Kleitman. Point selections and weak e-nets for convex hulls. Combinatorics, Probability & Computing, 1:189-200, 1992.
- B. Aronov, B. Chazelle, and H. Edelsbrunner. Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry, 6:435-442, 1991. URL: http://dx.doi.org/10.1007/BF02574700.
-
B. Bukh, J. Matoušek, and G. Nivasch. Lower bounds for weak epsilon-nets and stair-convexity. Israel Journal of Mathematics, 182(1):199-228, 2011.
- J.L. De Carufel, M. Katz, M. Korman, A. van Renssen, M. Roeloffzen, and S. Smorodinsky. On kinetic range spaces and their applications. CoRR, abs/1507.02130, 2015. URL: http://arxiv.org/abs/1507.02130.
-
B. Chazelle, H. Edelsbrunner, M. Grigni, L.J. Guibas, M. Sharir, and E. Welzl. Improved bounds on weak epsilon-nets for convex sets. Discrete & Computational Geometry, 13:1-15, 1995.
- B. Chazelle, H. Edelsbrunner, M. Grigni, L.J. Guibas, M. Sharir, and E. Welzl. Improved bounds on weak epsilon-nets for convex sets. Discrete & Computational Geometry, 13:1-15, 1995. URL: http://dx.doi.org/10.1007/BF02574025.
- D. Haussler and E. Welzl. epsilon-nets and simplex range queries. Discrete & Computational Geometry, 2:127-151, 1987. URL: http://dx.doi.org/10.1007/BF02187876.
-
J. Matoušek and U. Wagner. New constructions of weak epsilon-nets. Discrete & Computational Geometry, 32(2):195-206, 2004.
- N.H. Mustafa and S. Ray. Weak epsilon-nets have basis of size o(1/epsilon log(1/epsilon)) in any dimension. Comput. Geom., 40(1):84-91, 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2007.02.006.
-
A. Ya. Chervonenkis V. N. Vapnik. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264-280, 1971.