  Huffman Codes are optimal Instantaneous Fixed-to-Variable (FV) codes in which
every source symbol can only be encoded by one codeword. Relaxing these
constraints permits constructing better FV codes. More specifically, recent
work has shown that AIFV-$m$ codes can beat Huffman coding. AIFV-$m$ codes
construct am $m$-tuple of different coding trees between which the code
alternates and are only almost instantaneous (AI). This means that decoding a
word might require a delay of a finite number of bits.
  Current algorithms for constructing optimal AIFV-$m$ codes are iterative
processes that construct progressively "better sets" of code trees. The
processes have been proven to finitely converge to the optimal code but with no
known bounds on the convergence rate.
  This paper derives a geometric interpretation of the space of binary AIFV-$2$
codes, permitting the development of the first polynomially time-bounded
iterative procedures for constructing optimal AIFV codes.
  We first show that a simple binary search procedure can replace the current
iterative process to construct optimal binary AIFV-$2$ codes. We then describe
how to frame the problem as a linear programming with an exponential number of
constraints but a polynomial-time separability oracle. This permits using the
Gr\"otschel, Lov\'asz and Schrijver ellipsoid method to solve the problem in a
polynomial number of steps. While more complicated, this second method has the
potential to lead to a polynomial time algorithm to construct optimal AIFV-$m$
codes for general $m$.
