The changes of the local structure of water are investigated with increasing temperature and decreasing density from ambient conditions up to the critical point. The local structure around the molecules is analyzed in terms of the properties of the Voronoi polyhedra (VP) of the molecules. For reference, the entire analysis is also performed in liquid H2S. In this way, the effect of the hydrogen bonding on the local structure can also be studied. In determining the VP of the molecules an exact algorithm is used. In analyzing the local structure it is found that the decrease of the density not only leads to the increase of the free volume available for the molecules, but it also increases the volume of the voids present in the system. A linear relation is found between the average free volume of the molecules and the average volume of the vacancies, the latter being always about the double of the former. The comparison of the results concerning the shape of the VP of the molecules obtained for water at different thermodynamic state points and for liquid H2S clearly reveals that even above the critical point, hydrogen bonds are still playing a very important role in forming the molecular level structure of water. It is also found that the tetrahedral arrangement of the nearest-neighbor molecules, which is a characteristic feature of the water structure under ambient conditions, already disappears at temperatures well below the critical point, and the relative arrangement of the first four nearest-neighbor molecules becomes rather similar to that in liquid H2S.