In this study is presented a general algorithm for computing Voronoi volumes of atoms or group of atoms in condensed phases. The method is essentially an extension of the Medvedev procedure to allow vertice determination for any Voronoi polyhedron, primitive or with degenerate vertices. The algorithm has been employed for computing time-averaged volumes in the hydrated crystal of met-myoglobin, using the data of a molecular dynamics simulation. The results, compared to previous volume determination in myoglobin, emphasize the fundamental role of solvent structure close to the protein surface in relation to the packing density properties of the residues. Relative volumes fluctuations of myoglobin residues have been found to be correlated to the corresponding mean square displacements from X-ray diffraction studies and to the theoretical hydration energies.