Most proteins fulfill their functions through the interaction with other proteins. Because most of these interactions are transitory, they are difficult to detect experimentally, and obtaining the structure of the complex is generally not possible. Consequently, prediction of the existence of these interactions and of the structure of the resulting complex has received a lot of attention in the last decade. However, proteins are very complex objects, and classical computing methods have lead to computer-time consuming methods, whose accuracy is not sufficient for largescale exploration of the so-called “interactome”, the ensemble of protein-protein complexes in the cell. In order to design an accurate and high-throughput prediction method for protein-protein docking, the first step was to model a protein structure using a formalism allowing fast computation, without losing the intrinsic properties of the object. In our work, we have tested two different, but related, formalisms: the Voronoi and Laguerre tessellations. We present here a comparison of these two models in the context of protein-protein docking.