  Border bases arise as a canonical generalization of Gr\"obner bases. We
provide a polyhedral characterization of all order ideals (and hence border
bases) that are supported by a zero-dimensional ideal: order ideals that
support a border basis correspond one-to-one to integral points of the order
ideal polytope. In particular, we establish a crucial connection between the
ideal and its combinatorial structure. Based on this characterization we adapt
the classical border basis algorithm to allow for computing border bases for
arbitrary order ideals, which are independent of term orderings. We also show
that finding a maximum weight order ideal that supports a border basis is
NP-hard, and that the convex hull of admissible order ideals has no polynomial
polyhedral description.
