Complementary vertices and adjacency testing in polytopes

Details Complementary vertices and adjacency testing in polytopes Complementary vertices and adjacency testing in polytopes

2012-02-18

arxiv.org/abs/1202.4045v1

Mathematics

Combinatorics

12 pages, 5 figures

Scientific paper

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 a second such pair. 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 Rn | 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.

Affiliated with

Also associated with

No associations

Rating

Complementary vertices and adjacency testing in polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complementary vertices and adjacency testing in polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complementary vertices and adjacency testing in polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32966