Asymmetric Convex Intersection Testing (ACIT)

Orateur: Wolfgang MULZER
Localisation: Université libre de Berlin, Allemagne
Type: Groupe de travail théorie du min-max
Site: UPEM , 4B 107
Date de début: 26/03/2019 - 15:30
Date de fin: 25/03/2019 - 16:30

Let $P$ be a set of $n$ points and $H$ a set of $n$ halfspaces in $d$ dimensions.
We denote by $ch(P)$ the polytope obtained by taking the convex hull of $P$,
and by $fh(H)$ the polytope obtained by taking the intersection of the
halfspaces in $H$. Our goal is to decide whether the intersection of $H$ and
the convex hull of $P$ are disjoint. Even though ACIT is a natural variant
of classic LP-type problems that have been studied at length in the
literature, and despite its applications in the analysis of
high-dimensional data sets, it appears that the problem has not been
studied before.
We discuss how known approaches can be used to attack the ACIT problem,
and we provide a very simple strategy that leads to a deterministic
algorithm, linear on $n$ and $m$, whose running time depends reasonably on
the dimension $d$.

Based on joined work with Luis Barba.