Barany, I;
Mustafa, NH;
(2020)
An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets.
Computational Geometry
, 90
, Article 101649. 10.1016/j.comgeo.2020.101649.
Preview |
Text
weakepsnetsnote(2).pdf - Accepted Version Download (312kB) | Preview |
Abstract
We show that, as a consequence of a new result of Pór on universal Tverberg partitions, any large-enough set Pof points in Rdhas a (d +2)-sized subset whose Radon point has half-space depth at least cd·|P|, where cd∈(0, 1)depends only on d. We then give two applications of this result. The first is to computing weak e-nets by random sampling. The second is to show that given any set P of points in Rdand a parameter e>0, there exists a set of O (e−⌊d2⌋+1)⌊d2⌋-dimensional simplices (ignoring polylogarithmic factors) spanned by points of Psuch that they form a transversal for all convex objects containing at least e·|P|points of P.
| Type: | Article |
|---|---|
| Title: | An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.comgeo.2020.101649 |
| Publisher version: | https://doi.org/10.1016/j.comgeo.2020.101649 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Tverberg’s theorem, Radon’s lemma, weak e-nets, half-space depth, transversals |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10103537 |
Archive Staff Only
 |
View Item |
