3
$\begingroup$

I have a sequence of convex sets $C_\lambda$ for $\lambda \in \mathbb{R}$ such that for $\lambda_1 > \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$.

$\endgroup$
  • $\begingroup$ Do you have any information about the size of each convex set? $\endgroup$ – Jeremy Sep 6 '13 at 22:48
1
$\begingroup$

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 > \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.

$\endgroup$
  • $\begingroup$ You could use doubling search too, if the sizes of the convex sets increase with $\lambda$: test the convex sets $1$,$2$,$4$,$8$,... till you find one that contains $x$, then binary search in the last interval you found. $\endgroup$ – Jeremy Sep 6 '13 at 22:50
  • $\begingroup$ @Jeremy, yup! That was implicitly what I had in mind for the case where we have an infinite family of convex sets. (That's where the dependence on $|f(x)|$ comes from, in my answer.) $\endgroup$ – D.W. Sep 6 '13 at 22:58
  • $\begingroup$ D.W. and Jeremy : Yes, the binary search is the first thing that came to my mind too. Was wondering if one can do any better. As for the representation of the set - I have some flexibility: if any particular representation would lead to a significantly better algorithm I would prefer that; in fact that is an interesting question in itself I guess. And it is an infinite sequence. $\endgroup$ – Kcafe Sep 9 '13 at 21:15
  • $\begingroup$ @Krishna, I encourage you to edit the question to clarify all of those points; that will increase the exposure your question gets. On this site, the expectation is that people should be able to understand your question and all of your requirements just by reading the main body of the question, without reading the comment thread. You can do that by clicking the "edit" link underneath your question. (Given that it's an infinite sequence, it also might not hurt to describe how you are currently representing the sets, as I'm still not clear on the structure of your infinite sequence of sets.) $\endgroup$ – D.W. Sep 9 '13 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.