Epsilon-Nets for Halfspaces Revisited

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.

• Publication year

  2014

• Venue

  Unknown venue

• Publication date

  2014-10-12

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1410.3154
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• Related variants are also addressed, including the case of points and pseudo-disks in the plane.

  Confidence 0.91

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• The five proofs are presented as simpler than previous proofs.

  Confidence 0.84

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• Five proofs are given for the ε-net theorem over halfspace ranges.

  Confidence 0.96

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• For any ε > 0, any set P of n points in R^3 admits an ε-net for halfspace ranges of size O(1/ε).

  Confidence 0.99

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review

• five proofs

  method, proof strategy

  A set of five independent proof constructions used to establish the same result.

  Aliases: five separate proofs

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• halfspace range

  range family, geometric object

  A range defined by all points on one side of a plane, used here as the family of query sets.

  Aliases: halfspace ranges, halfspaces

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• o(1/ε) size

  complexity bound, asymptotic guarantee

  An asymptotic size bound that scales proportionally to 1 divided by ε.

  Aliases: inverse-epsilon bound, linear inverse-epsilon size

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• points and pseudo-disks in the plane

  problem variant, geometric setting

  A related two-dimensional variant where the study combines point sets with pseudo-disk geometric ranges.

  Aliases: planar pseudo-disk variant, points with pseudo-disks

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• point set in r^3

  problem setting, input model

  The finite input collection of n points considered in three-dimensional Euclidean space.

  Aliases: 3D point set, P in R^3

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• simpler than previous proofs

  contribution, comparison

  A comparative claim that the presented derivations use less complicated arguments than earlier known proofs.

  Aliases: simpler than prior proofs, arguably simpler proofs

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review
• ε-net

  geometric concept, combinatorial structure

  A selected subset of points that intersects every halfspace range meeting the required coverage condition in the studied range family.

  Aliases: epsilon-net, epsilon net

  imjlk (vdp8mqzes2) extractionAnonymous (12632b8b5f) review뀨 (7c402c1b98) review박진우 (dztg5apj7m) review

• Tight lower bounds for the size of epsilon-nets

  2010cited by this paper
• Polychromatic coloring for half-planes

  2010cited by this paper
• Improved Approximation for Guarding Simple Galleries from the Perimeter

  2010cited by this paper
• A Non-linear Lower Bound for Planar Epsilon-nets

  2010cited by this paper
• Small-size ε-nets for axis-parallel rectangles and boxes

  2009cited by this paper
• New existence proofs ε-nets

  2008influential reference
• Combinatorial Geometry

  2006cited by this paper
• Improved Approximation Algorithms for Geometric Set Cover

  2005influential reference
• Lectures on discrete geometry

  2002cited by this paper
• Derandomization in Computational Geometry

  1996influential reference
• A new technique for analyzing substructures in arrangements of piecewise linear surfaces

  1996cited by this paper
• Computing many faces in arrangements of lines and segments

  1994cited by this paper
• Backwards Analysis of Randomized Geometric Algorithms

  1993cited by this paper
• Reporting Points in Halfspaces

  1992influential reference
• On Spanning Trees with Low Crossing Numbers

  1992cited by this paper
• Almost tight bounds forɛ-Nets

  1992cited by this paper
• Efficient partition trees

  1991cited by this paper
• How to net a lot with little: small ε-nets for disks and halfspaces

  1990influential reference
• Construction of ɛ-nets

  1990cited by this paper
• A deterministic view of random sampling and its use in geometry

  1988cited by this paper
• Epsilon-Nets for Halfplanes

  1988cited by this paper
• Applications of random sampling in computational geometry, II

  1988cited by this paper
• ɛ-nets and simplex range queries

  1987influential reference
• New applications of random sampling in computational geometry

  1987cited by this paper

• Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges

  2019cites this paper
• A Simple Proof of Optimal Epsilon Nets

  2018cites this paper
• A Simple Proof of Optimal Epsilon Nets

  2017cites this paper
• Tighter Estimates for epsilon-nets for Disks

  2015cites this paper
• Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings

  2015cites this paper
• 2 Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings 1 . 1 Standard Cuttings

  2015cites this paper
• A PTAS for the Weighted Unit Disk Cover Problem

  2015cites this paper
• Subsampling in Smoothed Range Spaces

  2015cites this paper