Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Hitting Simplices with Points in $R^3$
 
research article

Hitting Simplices with Points in $R^3$

Basit, Abdul
•
Mustafa, Nabil H.
•
Ray, Saurabh  
Show more
2010
Discrete & Computational Geometry

The so-called first selection lemma states the following: given any set P of n points in a"e (d) , there exists a point in a"e (d) contained in at least c (d) n (d+1)-O(n (d) ) simplices spanned by P, where the constant c (d) depends on d. We present improved bounds on the first selection lemma in a"e(3). In particular, we prove that c (3)a parts per thousand yen0.00227, improving the previous best result of c (3)a parts per thousand yen0.00162 by Wagner (On k-sets and applications. Ph.D. thesis, ETH Zurich, 2003). This makes progress, for the three-dimensional case, on the open problems of Bukh et al. (Stabbing simplices by points and flats. Discrete Comput. Geom., 2010) (where it is proven that c (3)a parts per thousand currency sign1/4(4)a parts per thousand 0.00390) and Boros and Furedi (The number of triangles covering the center of an n-set. Geom. Dedic. 17(1):69-77, 1984) (where the two-dimensional case was settled).

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00454-010-9263-2
Web of Science ID

WOS:000280905600010

Author(s)
Basit, Abdul
Mustafa, Nabil H.
Ray, Saurabh  
Raza, Sarfraz
Date Issued

2010

Published in
Discrete & Computational Geometry
Volume

44

Issue

3

Start page

637

End page

644

Subjects

Centerpoint

•

Selection lemma

•

Simplex

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
DCG  
Available on Infoscience
November 26, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/59215
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés