4
$\begingroup$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion.

Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the finite set of points in $\mathbb{R^3}$, and let $C = Hull(M)$ be the convex hull of it. The set $M$ is said to be in extreme state, if $A_i \in \partial C$ for each $i = 1, \ldots, n$.

In the other words, points are in extreme state, if none of them lie in the internal part of their convex hull.

There is an evident criterion of convexity:

Proposition. Set of points $M = \{A_{1}, \ldots, A_{n}\}$ in $\mathbb{R^3}$ is in extreme state iff the following condition holds for each $i = 1, \ldots, n,\;\;\;j = 1, \ldots, n,\;\;\;i \neq j$: $$ h_i \ge (u_i, u_j)h_j $$ where $A_i = h_i u_i, \;\;\; h_i \in \mathbb{R}, h_i > 0, u_i \in \mathbb{R}^3, ||u_i|| = 1$

The geometric sense of this condition is that $i$-th point must have the biggest projection to $i$-th direction, compared with projections of other points: $(u_i, h_i u_i) \ge (u_i, h_j u_j)$

The drawback of this criterion is that we need to check $n^2 - n$ inequalities, while most of them are redundant. For example, if $(u_i, u_j) < 0$, then corresponding condition can be omitted.

UPDATE: We need to have the least number of conditions, because they are going to be used as the linear conditions in the following QP problem:

$$ \sum \limits_{i = 1}^{n}||h_i - h^0_i||^2 \to min $$ where values $h_i^0$ are fixed.

The effective criterion is the criterion that has the least number of conditions.

Of course, it's evident that redundant conditions can be found as follows: For each $i = 1, \ldots, n,\;\;\;j = 1, \ldots, n,\;\;\;i \neq j$ solve the following LP problem: $$ I = h_i - (u_i, u_j)h_j \to min $$ with the set of linear constraints that includes all above conditions except $ h_i \ge (u_i, u_j)h_j $. And if $I_{min} \ge 0$, then this condition can be omitted.

But it does not seem good to run simplex method $n^2 - n$ times.

Maybe there exists more smart approach for redundant conditions elimination for this problem?

$\endgroup$
  • 1
    $\begingroup$ There are quite a few convex hull computation algorithms out there. Have you looked at those; and if not, why are they insufficient? $\endgroup$ – Michael Grant Nov 3 '14 at 18:56
  • $\begingroup$ @MichaelGrant, yes, of course i looked at them. But the problem is stated not as computation of a convex hull. We need explicit conditions for points to be in extreme state. These two problems are quite different. $\endgroup$ – Ilya Palachev Nov 4 '14 at 11:48
  • 1
    $\begingroup$ Ah, I think I understand now. I am afraid I do not have anything to offer you. What are your optimization variables, then? If they are $A_i$ then I see no way to represent the extreme constraint condition as "linear conditions". For instance, $h_i\geq(u_i,u_j)h_j$ is not linear, and the requirement that $\|u_i\|_2=1$ is not convex. Subsitution of $A_i$ and $A_j$ back in does not resolve the problem. $\endgroup$ – Michael Grant Nov 4 '14 at 13:39
  • 1
    $\begingroup$ So the directions are fixed, but only the radii are variable? Interesting. Seems like something could be done there to take advantage of that. $\endgroup$ – Michael Grant Nov 4 '14 at 14:05
  • 4
    $\begingroup$ It seems that the “only if” part of Proposition does not hold. For instance, if $A_i$ are vertices of a small convex polyhedron shifted far away from the origin $0$ then all $i$-th directions are almost parallel, so only the farthest point would have the biggest projection to its direction. A precise example to check maybe is $A_1=(100,100,0)$, $A_2=(101,100,0)$, $A_3=(100,101,0)$, and $A_4=(101,101,0)$. $\endgroup$ – Alex Ravsky Oct 20 '17 at 5:40

Your Answer

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

Browse other questions tagged or ask your own question.