VORONOI DIAGRAMS IN A RIVER
- 1 March 1992
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 2 (1) , 29-48
- https://doi.org/10.1142/s0218195992000032
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: