A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space

DOI10.1016/j.ipl.2010.06.005zbMath1234.68441MaRDI QIDQ407569

Esther Ezra

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.06.005

zbMATH Keywords

computational geometry; \(\epsilon \)-nets; \(d\)-layer range-trees; geometric range spaces

Mathematics Subject Classification ID

52B55: Computational aspects related to convexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Tight lower bounds for the size of epsilon-nets, Piercing axis-parallel boxes, On weak \(\epsilon\)-nets and the Radon number

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds for weak epsilon-nets and stair-convexity
• A non-linear lower bound for planar epsilon-nets
• A deterministic view of random sampling and its use in geometry
• Improved approximation algorithms for geometric set cover
• Improved bounds on the union complexity of fat objects
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• New constructions of weak \(\varepsilon\)-nets
• Dynamic data structures for fat objects and their applications
• Efficient Colored Orthogonal Range Counting
• Computing Many Faces in Arrangements of Lines and Segments
• Polynomial-time approximation schemes for packing and piercing fat objects
• Small-size ε-nets for axis-parallel rectangles and boxes
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects