Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations. I. Theoretical foundations. (English. Russian original) Zbl 1327.90261
Cybern. Syst. Anal. 51, No. 3, 325-335 (2015); translation from Kibern. Sist. Anal. 2015, No. 3, 3-15 (2015).
Summary: This article considers a method for constructing Voronoi diagrams and their generalizations on the basis of the unified approach that consists of formulating a continuous optimal set partitioning problem with a partition quality criterion that provides appropriate types of Voronoi diagrams and applying the mathematical and algorithmic apparatus to solve such problems. This approach provides the ability not only to construct well-known Voronoi diagrams but also to design new ones.
MSC:
| 90C27 | Combinatorial optimization |
Keywords:
Voronoi diagram; continuous problem of optimal partitioning of sets from \(E_n\); Shor’s \(r\)-algorithmReferences:
| [1] | G. F. Voronoi, Collected Works [in Russian], Vol. 2, Izd. Akad. Nauk UkrSSR, Kiev (1952). · Zbl 0049.02804 |
| [2] | A. H. Thiessen, “Precipitation averages for large areas,” Monthly Weather Review, 39, No. 7, 1082-1084 (1911). |
| [3] | F. G. Tóth, “Multiple packing and covering of spheres,” Acta Mathematica Academiae Scientiarum Hungarica, 34, Nos. 1-2, 165-176 (1979). · Zbl 0444.52010 · doi:10.1007/BF01902605 |
| [4] | S. V. Terekhov, Modeling Thermal and Kinetic Properties of Real Systems [in Russian], Weber, Donetsk (2007). |
| [5] | R. Klein, “Concrete and abstract Voronoi diagrams,” Lecture Notes in Computer Science, 400, Springer (1987). · Zbl 0699.68005 |
| [6] | I. Ya. Akimova, “Application of Voronoi diagrams in combinatorial problems: A survey,” Izv. Akad Nauk SSSR, Tekhn. Kibern., No. 2, 102-109 (1984). · Zbl 0713.05051 |
| [7] | I. Ya. Akimova, “The problem of optimal placement and generalizations of a theorem of Fejes L. Tóth,” Izv. Akad Nauk SSSR, Tekhn. Kibern., No. 2, 224-228 (1982). · Zbl 1370.76149 |
| [8] | F. Preparata and M. Shamos, Computational Geometry: An Introduction [Russian translation], Mir, Moscow (1989). · Zbl 0744.68131 |
| [9] | A. G. Sukharev, Minimax Algorithms in Numerical Analysis [in Russian], Nauka, Moscow (1989). · Zbl 0717.65037 |
| [10] | E. M. Kiseleva and T. F. Stepanchuk, “Choice of optimal coefficients and optimal nodes of quadrature formulas for functional classes given by quasimetrics,” Probl. Upravl. Inf., No. 3, 138-153 (2002). |
| [11] | E. M. Kiseleva, L. I. Lozovskaya, and E. V. Timoshenko, “Solution of continuous problems of optimal covering with spheres using optimal set-partition theory,” Cybernetics and Systems Analysis, 45, No. 3, 421-437 (2009). · Zbl 1182.49045 · doi:10.1007/s10559-009-9113-5 |
| [12] | V. S. Brusov and S. A. Piyavskii, “A computational algorithm for optimally covering a plane region,” Zh. Vychisl. Mat. Mat. Fiz., 11, No. 2, 304-312 (1971). |
| [13] | L. F. Tóth, Packing in a Plane, on a Sphere, and in a Space [Russian translation], GIFML, Moscow (1958). |
| [14] | Koryashkina, LS, Solution to a problem of optimal placement of an industrial enterprise, 65-69 (1999), Dnipropetrovsk |
| [15] | H. Ledoux and M. Christopher, “Gold modelling three-dimensional geoscientific fields with the Voronoi diagram and its dual,” International Journal of Geographical Information Science, 22, No. 5, 547-574 (2008). · doi:10.1080/13658810701517120 |
| [16] | I. Menelaos and M. Yvinec, “Dynamic additively weighted Voronoi diagrams in 2D,” Technical Report ECG-TR-122201-01, INRIA, Sophia-Antipolis; 10th European Symposium on Algorithms, Sophia Antipolis, France (2002), pp. 586-598. · Zbl 1019.68608 |
| [17] | Laver, M.; Sergenti, E.; Schilperoord, M.; Seth, A. (ed.); Prescott, T. (ed.); Bryson, J. (ed.), Endogenous birth and death of political parties in dynamic party competition (2010), Cambridge |
| [18] | E. M. Kiseleva and L. S. Koryashkina, Models and Methods for Solving Continuous Problems of Optimal Set Partitioning: Linear, Nonlinear, and Dynamic Problems [in Russian], Naukova Dumka, Kyiv (2013). · Zbl 1004.49018 |
| [19] | A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd Edition, Wiley, West Sussex (England) (2000). · Zbl 0946.68144 · doi:10.1002/9780470317013 |
| [20] | F. Aurenhammer and R. Klein, “Voronoi diagrams: A survey of a fundamental geometric data structure,” ACM Computing Surveys, 23, No. 3, 345-405 (1991). · doi:10.1145/116873.116880 |
| [21] | E. M. Kiseleva and N. Z. Shor, Continuous Problems of Optimal Set Partitioning: Theory, Algorithms, and Applications [in Russian], Naukova Dumka, Kyiv (2005). |
| [22] | Yoshiaki Ohsawa, “A geometrical solution for quadratic bicriteria location models,” European Journal of Operational Research, 114, 380-388 (1999). · Zbl 0957.90080 · doi:10.1016/S0377-2217(98)00187-8 |
| [23] | S. I. Trubin, “Information space mapping with adaptive multiplicatively weighted Voronoi diagrams,” M.S. Thesis, 6, No. 2, 123-138, Oregon State University (2007). · Zbl 1209.68585 |
| [24] | I. Ya. Akimova and A. P. Akimov, “Weighted Voronoi partitions,” Izv. Akad. Nauk SSSR, Tekhn. Kibern., No. 3, 186-190 (1988). · Zbl 0719.05007 |
| [25] | Jooyandeh Mohammadreza, Mohades Ali, and Mirzakhah Maryam, “Uncertain Voronoi diagram,” Information Processing Letters, 109, No. 13, 709-712 (2009). · Zbl 1209.68585 · doi:10.1016/j.ipl.2009.03.007 |
| [26] | M. Balzer, “Capacity-constrained Voronoi diagrams in continuous spaces,” in: The International Symposium on Voronoi Diagrams in Science and Engineering (2009). · Zbl 1325.52016 |
| [27] | E. M. Kiseleva, “An algorithm for solving the problem of optimal partitioning under constraints,” Cybernetics, 19, No. 1, 115-120 (1983). · Zbl 0531.90075 |
| [28] | E. Bakolas and P. Tsiotras, “The Zermelo-Voronoi diagram: A dynamic partition problem,” Automatica, 46, No. 12, 2059-2067 (2010). · Zbl 1206.90204 · doi:10.1016/j.automatica.2010.09.003 |
| [29] | L. B. Hashemi, M. A. Mostafavi, and J. Pouliot, “Dynamic field process simulation within GIS: The Voronoi approach,” in: The International Archives of the Photogrammetry, Remote Sensing, and Spatial Information Sciences, Vol. XXXVII, Part B2, Beijing (2008), pp. 891-897. |
| [30] | B. Lau, C. Sprunk, and W. Burgard, “Efficient grid-based spatial representations for robot navigation in dynamic environments,” Robotics and Autonomous Systems, 61, No. 10, 1116-1130 (2013). · doi:10.1016/j.robot.2012.08.010 |
| [31] | Kikuo Fujita, Noriyasu Hirokawa, and Tomoya Tachikawa, “Voronoi diagram based cumulative approximation for engineering optimization,” in: AIAA-2000-4919, Department of Computer-Controlled Mechanical Systems, Graduate School of Engineering, Osaka University, Suita, Osaka 565-0871, Japan (2000), pp. 1-11. |
| [32] | T. Nishida, K. Sugihara, and M. Kimura, “Stable marker-particle method for the Voronoi diagram in a flow field,” Journal of Computational and Applied Mathematics, 202, No. 2, 377-391 (2007). · Zbl 1370.76149 · doi:10.1016/j.cam.2006.01.035 |
| [33] | N. Z. Shor, Methods of Minimization of Nondifferentiable Functions and Their Applications [in Russian], Naukova Dumka, Kyiv (1979). · Zbl 0524.49002 |
| [34] | N. Z. Shor, T. A. Bardadym, N. G. Zhurbenko, A. P. Lykhovid, and P. I. Stetsyuk, “Nonsmooth-optimization methods in problems of stochastic programming,” Cybernetics and Systems Analysis, 35, No. 5, 708-720 (1999). · Zbl 0961.68027 · doi:10.1007/BF02733404 |
| [35] | N. Z. Shor and S. I. Stetsenko, Quadratic Extremal Problems and Nondifferentiable Optimization [in Russian], Naukova Dumka, Kyiv (1989). |
| [36] | N. Z. Shor and P. I. Stetsyuk, “Modified <Emphasis Type=”Italic“>r-algorithm to find the global minimum of polynomial functions,” Cybernetics and Systems Analysis, 33, No. 4, 482-497 (1997). · Zbl 0916.90248 · doi:10.1007/BF02733104 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
