DIMACS 
Advisors
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 ndimensional 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 ndimensional space where one side of an n1dimensional hyperplane has been removed. We can describe the problem using the following system of inequalities:
The Vertex Enumeration problem is equivalent to the problem of determining whether zero is in the convex hull formed by a_{1}...a_{n} 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; 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 subcollection of vectors that cannot be separated into open halfspace, etc. So, if we have a collection of vectors a_{1},…,a_{n}, define a matrix A to be a list of transposes of a_{1},…,a_{n}.
┌
┐
│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 a_{1},…,a_{n} with this property is equivalent to finding all possible antibodies. Recently, Vladimir Gurvich proved that this problem is NPhard. However, if we replace ≥ sign with > and consider maximal subsets of a_{1},…,a_{n}, than the problem is changed to enumeration of antisimplices. Currently, we are looking for efficient algorithms to generate and/or identify simplices, antisimplices, bodies, and antibodies 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]
