Research On Power Diagram-Based Variational Optimization Applications

Given a question, the varational optimization aims at building a target function and founding the extreme value of this function. Variational optimization algorithm is a discipline that is widely applied in economical planning, engineering design, production management, transportation, national defense security and so on. What’s more, it has attracted more attention from the government. However, as the problems are becoming more and more complex, the traditional optimization algorithms are not able to solve these problems. For different problems, we should adopt different methods.Power diagram is generalized from Voronoi diagram. Power diagram is an important research content in computational geometry. As power diagram can be treated as Voronoi diagram of circles, so it is suited for solving the problems related to circles or spheres. As a result, this thesis mainly focuses on the variational optimization algorithm based on power diagram. In this thesis, we design optimization algorithm for two concrete problems, i.e., Poisson disk sampling and density-aware sensor coverage.Poisson disk sampling is one important research topic in computer graphics. A Poisson disk distribution is a point set in which the distance between two arbitrary points is no less than one definite value. As Poisson disk distribution has two properties: randomness and uniformness, i.e., blue noise properties, it is widely used in rendering, ray tracing, object distribution and other fields. The traditional algorithms for Poisson disk sampling is based on Lloyd and "dart throwing". Lloyd relaxation method can generate uniform distributions, but it breaks the random property, "dart throwing method" can guarantee the random property, but it breaks the uniform property. In this thesis, we propose one algorithm based on disk packing, which can preserve both two properties. What’s more, we also generalize our algorithm for non-uniform sampling, i.e., stippling. Our algorithm can generate nature stippling results with less regular patterns.The traditional methods for sensor deployment assumes that the probability of event happening is uniform. However, this is not exact in real life. Load balancing problem will come up, if we apply the existing methods to uneven monitored field. In this paper, we first propose the sensor deployment problem for uneven monitored field. We also design an optimization algorithm based on power diagram. Our algorithm can achieve a good balance between coverage and load balancing.