A Note on Testing Intersection of Convex Sets in Sublinear Time

Israela Solomon

We present a simple sublinear time algorithm for testing the following geometric property. Let $P_1,...,P_n$ be $n$ convex sets in ${\mathbb{R}}^d$ ($n\gg d$), such as polytopes,…