UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets

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. (In press). Green open access

[img]
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.ucl.ac.uk/id/eprint/10103537
Downloads since deposit
6Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item