Voronoi Diagrams And Its Applications

Voronoi diagram is a very important and practical geometric construction, and has great value. In this paper, we first make a minute discussion as to the Voronoi diagram on plane, and some method of constructing the diagram, especially the method of sweeping-line. Then the parts of triangular interpolates on the plane is also introduced. The airspace's sector partition is an importance of research at the domain of the airspace management. It has very important effects on increasing airspace's capability and ensuring security. With the aid of Voronoi diagram, we extend the method of sector optimum partition based on metamorphic Voronoi polygon to three-dimensional airspace, and optimization of combination of those finite elements is achieved based on the rule about balance of controller's workload. Then we extend the concept of Voronoi diagrams to parameterized surfaces, say the Voronoi diagrams on convex surfaces, the distance between two points on the surface is defined by the geodesic connecting them. We get a general divide-conquer method, especially to sphere; we compute the Voronoi diagram on the sphere. The method for constructing interpolates to data arbitrarily located on convex surfaces are based on the interpolation method of triangulation on surface, because of the complicity of triangulation, the price of compute is very high. So based on the Voronoi diagram on surface, especially , we presented an algorithm for constructing a smooth computable function f defined over the surface of a sphere and interpolating a set of n data valuesζi associated with n locations p i on the surface of the sphere.