# Getting a V-representation from an H-Representation of a polytope

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.

• $O(n^3)$, not $O(n!)$
– D.W.
Commented Aug 22, 2023 at 18:24
• Sorry you are correct since I fixed the dimensions Commented Aug 22, 2023 at 21:29
• 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. Commented Aug 23, 2023 at 17:51