Algorithm for testing if a point belongs to a sequence of convex set or not I have a sequence of convex sets $C_\lambda$ for $\lambda \in \mathbb{R}$ such that for $\lambda_1 &gt; \lambda_2$, we have $C_{\lambda_1} \subset C_{\lambda_2}$ (essentially a nested sequence of convex sets in $d$ dimensions). For a given point $x \in \mathbb{R}^d$, define: 
\begin{align*}
f(x) = \sup \{ \lambda: x \in C_{\lambda} \} 
\end{align*} 

Is there an efficient algorithm for computing $f(x)$ given $x$.
The obvious algorithm is to use binary search.

You'll need $\lg n$ iterations of binary search, where $n$ = the number of convex sets in your sequence.  (If you have an infinite family of convex sets, $\lg(|f(x)|/\epsilon)$ iterations are enough to approximate $f(x)$ to within $\epsilon$.)  In each iteration, for some value of $\lambda$, you test whether $x \in C_\lambda$.  You haven't specified the representation of the family of convex sets, but for typical representations, testing whether $x \in C_\lambda$ can be done in polynomial time.  So, the total running time will be polynomial.

To do better than this, I suspect the algorithm will need to depend upon how the sequence of convex sets $C$ is represented.  (Do you have a requirement for it to be represented in a particular way, or are you OK with any reasonable representation?  You might want to edit the question accordingly.  You might also want to specify whether this is a finite sequence or an infinite sequence, and how the sets are related.)



For instance, here's a special case where the problem is easier.  Suppose that the sequence of sets is represented as follows: you have a set of linear inequalities on $x_1,x_2,\dots,x_d,\lambda$, with constants $c_0,c_1,\dots,c_d$, so that each linear inequality has this form:

$$c_0 \lambda + c_1 x_1 + c_2 x_2 + \dots + c_d x_d \le 0.$$

Now suppose that the convex set $C_\lambda$ is defined as the set of points $(x_1,\dots,x_d)$ that satisfy all of these linear inequalities (notice the very specific kind of dependence on $\lambda$), and suppose that the linear inequalities are chosen so $C_{\lambda_1} \subset C_{\lambda_2}$ whenever $\lambda_1 &gt; \lambda_2$.  Then you compute $f(x)$ efficiently using a very simple algorithm: you plug in $x$ into each of the linear inequalities, leaving $\lambda$ as the only unknown in each case, and find the largest value of $\lambda$ so that all of those inequalities are satisfied.  This only works if your sets have a certain form and are represented in a certain special way, which is why I say that your problem will probably depend upon how the sets are represented and what structure they might have.