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$
  • $\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 Mar 22 '15 at 21:56
  • $\begingroup$ well, it would make sense to add vertices one by one... $\endgroup$ – Dima Pasechnik Mar 22 '15 at 22:11
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."
| cite | 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.

| cite | improve this answer | |
$\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.