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 i^th element of the first set is incident to the j^th element of the second set. The implementation of incidence matrices allows seamless switching back and forth between these views.

• Array< Set<int> >
  the simplest form of encoding of an incident structure. Obviously, you can take std::list or std::vector instead of Array, or substitute Set<int> by Bitset, if needed. The only disadvantage is the asymmetry between the relation operands: you can't query for all first-operand objects incident to a given second-operand object, without performing an exhaustive search over the whole structure.
• IncidenceMatrix
  two-dimensional grid of sets. The rows and columns (encoding the first and second operands respectively) have identical functionality, allowing for efficient iteration, search, insertion, and deletion of elements. The main disadvantage are rather high reallocation costs in the case of dynamical growth of an operand range (they are linear in the number of rows/columns.)
• FacetList
  two-dimensional grid of sets, optimized for queries of the following kind: `For a given element set, find all incidence sets that are included in or including it.' These queries, however, are possible only for the rows (first-operand incidence sets.) The columns have restricted functionality.