Complementary vertices and adjacency testing in polytopes
From MaRDI portal
Abstract: Our main theoretical result is that, if a simple polytope has a pair of complementary vertices (i.e., two vertices with no facets in common), then it has at least two such pairs, which can be chosen to be disjoint. Using this result, we improve adjacency testing for vertices in both simple and non-simple polytopes: given a polytope in the standard form {x in R^n | Ax = b and x geq 0} and a list of its V vertices, we describe an O(n) test to identify whether any two given vertices are adjacent. For simple polytopes this test is perfect; for non-simple polytopes it may be indeterminate, and instead acts as a filter to identify non-adjacent pairs. Our test requires an O(n^2 V + n V^2) precomputation, which is acceptable in settings such as all-pairs adjacency testing. These results improve upon the more general O(nV) combinatorial and O(n^3) algebraic adjacency tests from the literature.
Recommendations
- A criterion for the adjacency of vertices of polytopes generated by subsets of symmetric groups
- The maximum number of complementary facets of a simplicial polytope
- On the complexity of polytope isomorphism problems
- On-line and off-line vertex enumeration by adjacency lists
- A simple way to tell a simple polytope from its graph
Cited in
(3)
This page was built for publication: Complementary vertices and adjacency testing in polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914353)
