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.

Improve this question
$\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$
    – Alex Degtyarev
    Commented Mar 22, 2015 at 21:56
  • $\begingroup$ well, it would make sense to add vertices one by one... $\endgroup$
    – Dima Pasechnik
    Commented Mar 22, 2015 at 22:11

2 Answers 2

Reset to default
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."
Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .