Epsilon-nets for halfspaces revisited Academic Article uri icon

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

published in