Epsilon-Nets for Halfspaces Revisited
Har-Peled, Sariel · Kaplan, Haim · Sharir, Micha · Smorodinsky, Shakhar
Original · EN
Given a set P of n points in R³, we show that, for any ε >0, there exists an ε-net of P for halfspace ranges, of size O(1/ε). We give five proofs of this result, which are arguably simpler than previous proofs 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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.