---
_id: '4035'
abstract:
- lang: eng
  text: 'Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges
    of)S if, for any T⊆S containing εn points, the convex hull of T intersects W.
    We show the existence of weak ε-nets of size {Mathematical expression}, where
    β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al.
    Such a net can be computed effectively. We also consider two special cases: when
    S is a planar point set in convex position, we prove the existence of a net of
    size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular
    polygon, we use an argument from hyperbolic geometry to exhibit an optimal net
    of size O(1/ε), which improves a previous bound of Capoyleas.'
acknowledgement: The authors wish to express their gratitude for the support and hospitality
  of the DEC Palo Alto Systems Research Center.
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
  full_name: Chazelle, Bernard
  last_name: Chazelle
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Michelangelo
  full_name: Grigni, Michelangelo
  last_name: Grigni
- first_name: Leonidas
  full_name: Guibas, Leonidas
  last_name: Guibas
- first_name: Micha
  full_name: Sharir, Micha
  last_name: Sharir
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. Improved
    bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational Geometry</i>.
    1995;13(1):1-15. doi:<a href="https://doi.org/10.1007/BF02574025">10.1007/BF02574025</a>
  apa: Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Sharir, M., &#38; Welzl,
    E. (1995). Improved bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational
    Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02574025">https://doi.org/10.1007/BF02574025</a>
  chicago: Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas
    Guibas, Micha Sharir, and Emo Welzl. “Improved Bounds on Weak ε-Nets for Convex
    Sets.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1995. <a href="https://doi.org/10.1007/BF02574025">https://doi.org/10.1007/BF02574025</a>.
  ieee: B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl,
    “Improved bounds on weak ε-nets for convex sets,” <i>Discrete &#38; Computational
    Geometry</i>, vol. 13, no. 1. Springer, pp. 1–15, 1995.
  ista: Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. 1995. Improved
    bounds on weak ε-nets for convex sets. Discrete &#38; Computational Geometry.
    13(1), 1–15.
  mla: Chazelle, Bernard, et al. “Improved Bounds on Weak ε-Nets for Convex Sets.”
    <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1, Springer, 1995,
    pp. 1–15, doi:<a href="https://doi.org/10.1007/BF02574025">10.1007/BF02574025</a>.
  short: B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, E. Welzl,
    Discrete &#38; Computational Geometry 13 (1995) 1–15.
date_created: 2018-12-11T12:06:33Z
date_published: 1995-12-01T00:00:00Z
date_updated: 2022-06-13T12:37:06Z
day: '01'
doi: 10.1007/BF02574025
extern: '1'
intvolume: '        13'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02574025
month: '12'
oa_version: None
page: 1 - 15
publication: Discrete & Computational Geometry
publication_identifier:
  issn:
  - 0179-5376
publication_status: published
publisher: Springer
publist_id: '2094'
quality_controlled: '1'
status: public
title: Improved bounds on weak ε-nets for convex sets
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 13
year: '1995'
...