I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for $\mathbb{R}^3$

I implemented one which is very silly. Compute all possible intersections of 3 planes among all the half spaces. Then check it the resulting point is on the boundary of the polytope. If it is not, discard else keep. Then compute the CH of the result.

This works, it's also $O(n!)$ which is... less than ideal...

I am trying to read on Motzkin-Burger, Double Description and Bactracking, I can't seem to understand any.

Bactracking: The algorithm I would need seems to be $VertexEnum(R, S)$, but it requires a method for $RestrictedVertex$ and it seems, according to the paper, that that is an NP-Complete problem, so maybe there is no good solution? But that seems weird to me, that there truly is no more efficient way to go about it?

Another one I have heard of it the double precision algorithm, but again, finding an explanation that is more tractable than the paper has been... challenging.

  • $\begingroup$ $O(n^3)$, not $O(n!)$ $\endgroup$
    – D.W.
    Commented Aug 22, 2023 at 18:24
  • $\begingroup$ Sorry you are correct since I fixed the dimensions $\endgroup$
    – Makogan
    Commented Aug 22, 2023 at 21:29
  • 1
    $\begingroup$ Maybe you could take a look at Preparata and Muller, Finding the intersection of n half-spaces in time O(n log n), for some inspiration. $\endgroup$
    – Tassle
    Commented Aug 23, 2023 at 17:51


Your Answer

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