# Computionally efficient vertex enumeration for (convex) polytopes

Let $P \subseteq \mathbb{R}^d$ be an $\mathcal{H}$-polytope. The vertex enumeration problem asks for the set of vertices $V$ of $P$. Theoretically, the vertex enumeration problem for $P$ can be performed in $\mathcal{O}(|V|^{\lfloor d/2 \rfloor})$, cf. . Practically, one would use the double description method, cf. , and cf. cddlib for an implementation of the former.

In my application, I have to solve a rather large number of such vertex enumeration problems in let's say dimension $10$. Unfortunately, ccdlib is too slow and causes numerical problems (the GMP version is even slower).

Moreover, for my application it suffices to find a superset of $V$. Hence, I thought there might be a way to decompose $P$ into "simpler" polytopes such that the vertex enumeration for each such polytope could be performed much faster.

Is anybody aware of such method?

• How is the polytope defined? Is it given as an intersection of half-planes? If so, can this problem be transformed to the dual problem of enumerating all the facets of the convex hull if the vertices are given? Apr 27, 2015 at 9:17
• Yes, it is an $\mathcal{H}$-polytope, i.e., intersection of finitely many affine half-spaces. Yes, the facet and the vertex enumeration problem are strongly polynomial equivalent. Apr 27, 2015 at 10:10
{"ft_lang_label":"__label__en","ft_lang_prob":0.90623266,"math_prob":0.991889,"size":865,"snap":"2022-40-2023-06","text_gpt3_token_len":225,"char_repetition_ratio":0.1300813,"word_repetition_ratio":0.0,"special_character_ratio":0.24393064,"punctuation_ratio":0.12650603,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99954975,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-10-06T05:24:02Z\",\"WARC-Record-ID\":\"<urn:uuid:b1e3a5f8-c685-4d62-a0db-6a224f124f95>\",\"Content-Length\":\"110617\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:23433e38-f0ca-40b3-954e-08ac441710c8>\",\"WARC-Concurrent-To\":\"<urn:uuid:cec0d992-405e-4d26-84c2-6ad103e9160e>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/203966/computionally-efficient-vertex-enumeration-for-convex-polytopes\",\"WARC-Payload-Digest\":\"sha1:WKXT5R55PZNIPBJUWQH5EDD5MTR5GIO4\",\"WARC-Block-Digest\":\"sha1:G2557VT77FHIDVE5V2LWESEJPJ7ATWN2\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030337723.23_warc_CC-MAIN-20221006025949-20221006055949-00666.warc.gz\"}"}