1
$\begingroup$

How can we prove a point is an interior point of a convex set, considering we don't have all of the extreme points of the given convex set ?

or

How can we find an interior point of a convex set, considering we don't have all of the extreme points of the given convex set ? (convex combination of those extreme points would not work as it may belong to a 'edge' of that convex set)

$\endgroup$
  • 1
    $\begingroup$ What information do you have? $\endgroup$ – user21467 Oct 16 '14 at 17:25
0
$\begingroup$

Since you are saying you don't know all the extreme points of the convex set, presumably you have something like an oracle that will tell you whether a point belongs to the set or not. Given such an oracle, choose a random orthonormal basis $\{v_i\}$ and choose a really small $\epsilon$, and then for your point $x$ in question query the oracle to determine if $x \pm \epsilon v_i$ is contained in the set for all $v_i$ in the basis. If it is for all $\pm v_i$, then your point is in the interior. Otherwise if not all these points are contained in your set, you can keep reducing $\epsilon$ until you are confident your point is on the boundary, or at least very very close to it. Note in order for this to work you need your convex set to be full-dimensional.

$\endgroup$
  • $\begingroup$ Thanks! My question is if I choose some random basis, how can I make sure that the point you mentioned doesn't fall on the 'edge' of the set (which belongs to the convex set but it is not a relative interior point) $\endgroup$ – Faraz Ramtin Oct 18 '14 at 19:55
0
$\begingroup$

Empty sets are convex.

Moreover it depends on which topology you consider (e.g. $[0,1]\times \{0\}$ has empty interior in the Euclidean topology of $\mathbb{R}^2$, but non empty interior in the induced topology).

$\endgroup$

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.