3
$\begingroup$

Basically, we have an incremental sets of vertices

$${V_1} \subset {V_2} \subset ...$$

for each of them, we could build a polytope $${P_i} = Conv({V_i})$$

Consequently, we can compute

$${F_i} = Facet\left( {{P_i}} \right)$$

So my question is, what is the best numerical procedures to compute such $F_i$ from given ${V_1} \subset {V_2} \subset ...$ ? Thank you.

$\endgroup$
2
  • $\begingroup$ It seems to me that, a priori, there is absolutely no relation between $F_i$ and $V_{i-1}$. It may happen that $V_{i-1}$ is entirely in the interior of $P_i$. $\endgroup$ Mar 22, 2015 at 21:56
  • $\begingroup$ well, it would make sense to add vertices one by one... $\endgroup$ Mar 22, 2015 at 22:11

2 Answers 2

3
$\begingroup$

Perhaps this negative result will help focus your question.

Bremner, David. "Incremental convex hull algorithms are not output sensitive." Discrete & Computational Geometry. 21.1 (1999): 57-68.

  • "It turns out the order the points are inserted can make a huge di fference in the size of the intermediate polytopes. ... In this paper, we show that are families for which there is no polynomial insertion order."

But note this in the Conclusion:

  • "The question of the practical usefulness of the double description method is hardly settled by the existence of families without good insertion orders."
$\endgroup$
1
$\begingroup$

If you are allowed to generate the vertices one at a time, but the order is not fixed, this is very similar to this question, in which case you will find wisdom in the answers thereto.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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