# Epsilon-nets for halfspaces revisited Academic Article

•
• Overview
•
• Research
•
• View All
•

### abstract

• Abstract: Given a set $P$ of $n$ points in $\mathbb {R}^ 3$, we show that, for any $\varepsilon> 0$, there exists an $\varepsilon$-net of $P$ for halfspace ranges, of size $O (1/\varepsilon)$. We give five proofs of this result, which are arguably simpler than previous proofs\cite {msw-hnlls-90, cv-iaags-07, pr-nepen-08}. We also consider several related variants of this result, including the case of points and pseudo-disks in the plane. Subjects: Computational Geometry (cs. CG) Cite as: arXiv: 1410.3154 [cs. CG](or arXiv: 1410.3154 v1 [cs. CG] for this version) Submission history From: Sariel Har-Peled [view email][v1] Sun, 12 Oct 2014 21: 11: 48 GMT (19kb)

### publication date

• January 1, 2014