A new generalized Voronoi diagram is defined on the surface of a river with uniform flow; a point belongs to the territory of a site if and only if a boat starting from the site can reach the point faster than a boat starting from any other site. If the river runs slower than the boat, the Voronoi diagram has the same topological structure as the ordinary Voronoi diagram, and hence can be constructed from the ordinary Voronoi diagram by a certain transformation. If the river runs faster than the boat, on the other hand, the topological structure of the diagram becomes different from the ordinary one, but it can be constructed by the plane sweep technique. Moreover, Fortune’s plane sweep algorithm for constructing the ordinary Voronoi diagram can be interpreted as the algorithm for constructing the Voronoi diagram in a river in which the water flows at the same speed as the boat.