DIMACS

Home Page

 

Steven Jaslar Tatiana Yarmola
Rutgers, The State University of New Jersey University of California at Berkeley
sjaslar@dimax.rutgers.edu tyarmola@dimax.rutgers.edu
   

Advisors

Prof. Vladimir Gurvich Khaled Elbassioni William Cuckler
Rutcor, Rutgers University Rutcor, Rutgers University Mathematics Dept, Rutgers University
gurvich@rutcor.rutgers.edu elbassio@paul.rutgers.edu cuckler@math.rutgers.edu

 

We are currently working on the vertex enumeration of polytopes problem.  That is, we exploring ways to find the vertices of the polytope formed by an arbitrary finite set of intersecting half spaces in n-dimensional space.  A polytope is the region enclosed by a finite number of hyperplanes.  In this case, the hyperplanes are the borders of the open halfspaces.  A half space is simply a region of n-dimensional space where one side of an n-1-dimensional hyperplane has been removed.

We can describe the problem using the following system of inequalities:

a1T *  x1 + a2T * x2+ ... +an T *  xn  = b
x1, x2 ,...,xn ≥ 0

 

The Vertex Enumeration problem is equivalent to the problem of determining whether zero is in the convex hull formed by a1...an  Clearly, if zero is in the the convex hull of a set of points, than zero is in the convex hull of any superset of these points.  So enumeration of the minimal convex hulls that contain zero solves the problem of enumeration of all convex hulls that contain zero.

Let S be a set of points in n dimensional space.  Let X be subset of S.  We a call X a

simplex if X is a minimal set s.t. 0 belongs to a convex hull of X;
anti-simplex if X is a maximal set s.t. its convex hull does not contain 0;
body if X is a minimal set s.t 0 belongs to the interior of the convex hull of X;
anti-body if X is a maximal set s.t the interior of its convex hull does not contain 0
 

Alternatively, we can also define these objects using vectors.  For instance, assume we have a finite set of vectors. Then a simplex is the minimal sub-collection of vectors that cannot be separated into open half-space, etc.

So, if we have a collection of vectors a1,,an, define a matrix A to be a list of transposes of a1,,an.

                                ┐
                         a1T
                         a2T
                  A =   │
                         anT
                                ┘
 

Then the system of equations Ax 0, x 0 has a solution only if the collection of vectors a1,,an can be separated into closed half space. But often this system has no solution, and therefore we are interested in the subsets b1,,bk of a1,,an  s.t.

          ┐
   b1T
      │x 0 , x 0 has a solution.
   bkT
          ┘
 

Finding maximal subsets of a1,,an with this property is equivalent to finding all possible anti-bodies.  Recently, Vladimir Gurvich proved that this problem is NP-hard.  However, if we replace ≥ sign with > and consider maximal subsets of a1,,an, than the problem is changed to enumeration of anti-simplices.

Currently, we are looking for efficient algorithms to generate and/or identify simplices, anti-simplices, bodies, and anti-bodies in 2 dimensions.  In addition, we are looking for characterizations of 2 dimensional simplex hypergraphs -- that is, we are looking to see which sets of subsets of {1,2,3 ... n} can be realized as simplices in the plane.

Here is a link to our final presentation: [Final Presentation]

[Home Page]    
[Final Presentation]
 
For problems or questions regarding this web site contact sjaslar@dimax.rutgers.edu.
Last updated: 08/13/03.