Mathematics desk
< December 17	<< Nov \| December \| Jan >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 18

Finding adjacent vertices in a convex polytope

Given a convex polytope P defined as the intersection of half spaces $Ax\leq b$ , a vertex v of P, the others being unknown, is there an efficient algorithm to find all vertices of P which are adjacent to v? There are several well known algorithms for listing all the vertices of P, but considering the number of vertices may be huge compared to the number of faces it seems like you'd have a lot of wasted effort computing vertices which are not relevant. --RDBury (talk) 00:10, 18 December 2018 (UTC)[reply]

Actually the answer is to apply a vertex enumeration algorithm ot the vertex figure of v. Kind of obvious to me now, after thinking about it for a day or two. --RDBury (talk) 10:28, 19 December 2018 (UTC)[reply]