  In 2007, Eickmeyer et al. showed that the tree topologies outputted by the
Neighbor-Joining (NJ) algorithm and the balanced minimum evolution (BME) method
for phylogenetic reconstruction are each determined by a polyhedral subdivision
of the space of dissimilarity maps ${\R}^{n \choose 2}$, where $n$ is the
number of taxa. In this paper, we will analyze the behavior of the
Neighbor-Joining algorithm on five and six taxa and study the geometry and
combinatorics of the polyhedral subdivision of the space of dissimilarity maps
for six taxa as well as hyperplane representations of each polyhedral
subdivision. We also study simulations for one of the questions stated by
Eickmeyer et al., that is, the robustness of the NJ algorithm to small
perturbations of tree metrics, with tree models which are known to be hard to
be reconstructed via the NJ algorithm.
