
Suppose that you are given X1 ... Xm, a finite list of finite sets of points in 3-space, where each Xi has ni points. Let Ki denote the convex hull of Xi and let K be the intersection of all Ki. Your problem is to find the vertices of the polyhedron K.
Show that there is a randomized algorithm for this problem whose expected running time is O(n log n), where n = n1 + ... + nm.
To make the problem easier for now, assume that
you know that:
For example, if the string is 000, and if your algorithm looks at the first and third bits, it is done, since it knows the string is in L, without looking at the second bit, and its cost is then 2. On the other hand, if it looks at the first and second bits, it does not know whether the string is in L, and is forced to look at the third bit.
