An incidence structure encodes a binary function (x,y) ⇒ boolean with discrete, limited value sets of both operands x and y. Examples are vertex-facet incidence relation in a polyhedron, simplicial complex, etc. In Polymake Template Library, the objects of the incidence relation (vertices, facets, etc.) are always enumerated, so that the data structures have to deal with closed intervals of non-negative integers: [0..n-1].

An incidence structure can also be interpreted as a sparse matrix with boolean values, where an element (i,j) is true iff the ith element of the first set is incident to the jth element of the second set. The implementation of incidence matrices allows seamless switching back and forth between these views.