Polytope Approximation and Approximate Nearest Neighbor Queries (Cont.)

lecture to Friday. I will:

* Summarize the polytope separating algorithm of which I talked
on Tuesday

* Present an approach to "Linear Programming Queries" where many
queries with different linear functions are made to the same
linear set of linear constraints and the queries should be
answered efficiently. The query procedure follows the first
lp algorithm of clarkson that I presented.

* Present a result of Dudley:

Let P in R^d be a convex body contained in a ball of radius 1.
Then there is a polytope P' that contains P with

O(1/epsilon^{(d-1}/2})

facets so that the distance from any point in P' to P is at
most epsilon [this is relatively trivial if the 2 is removed
from the exponent; somewhat less with the 2 there]

Then this results will be used as part of Clarkson approach to
approximate nearest neighbor search on the following lecture.