A note about weak ε-nets for axis-parallel boxes in d-space

Agarwal, 1998, Computing many faces in arrangements of lines and segments, SIAM J. Comput., 27, 491, 10.1137/S009753979426616X N. Alon, A non-linear lower bound for planar epsilon-nets, in: Proc. 51st Annu. IEEE Sympos. Found. Comput. Sci., in press B. Aronov, E. Ezra, M. Sharir, Small-size ε-nets for axis-parallel rectangles and boxes, in: Proc. 41th Ann. ACM Symp. Theory Comput., 2009, pp. 639–648 B. Bukh, J. Matoušek, G. Nivasch, Lower bounds for weak ε-nets and stair-convexity, in: Proc. 25th Ann. ACM Symp. Comput. Geom., 2009, pp. 1–10 Chan, 2003, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms, 46, 178, 10.1016/S0196-6774(02)00294-8 Chazelle, 1995, Improved bounds on weak ε-nets for convex sets, Discrete Comput. Geom., 13, 1, 10.1007/BF02574025 Chazelle, 1990, A deterministic view of random sampling and its use in geometry, Combinatorica, 10, 229, 10.1007/BF02122778 Clarkson, 2007, Improved approximation algorithms for geometric set cover, Discrete Comput. Geom., 37, 43, 10.1007/s00454-006-1273-8 de Berg, 2008, Improved bounds on the union complexity of fat objects, Discrete Comput. Geom., 40, 127, 10.1007/s00454-007-9029-7 de Berg, 2008 Efrat, 2005, The complexity of the union of (α,β)-covered objects, SIAM J. Comput., 34, 775, 10.1137/S0097539702407515 Efrat, 2000, Dynamic data structures for fat objects and their applications, Comput. Geom. Theory Appl., 15, 215, 10.1016/S0925-7721(99)00059-0 Haussler, 1987, ε-Nets and simplex range queries, Discrete Comput. Geom., 2, 127, 10.1007/BF02187876 Kaplan, 2008, Efficient colored orthogonal range counting, SIAM J. Comput., 38, 982, 10.1137/070684483 Komlós, 1992, Almost tight bounds for epsilon nets, Discrete Comput. Geom., 7, 163, 10.1007/BF02187833 Matoušek, 2002 Matoušek Matoušek, 2004, New constructions of weak ε-nets, Discrete Comput. Geom., 32, 195, 10.1007/s00454-004-1116-4