On farthest Bregman Voronoi cells. (English) Zbl 1490.52006
Optimization 71, No. 4, 937-947 (2022); correction ibid. 73, No. 3, 897-898 (2024).
Given a strictly convex function \(g\) defined on an evenly convex set \(X \subseteq \mathbb{R}^n\) with nonempty interior, which is differentiable on the interior of \(X\), the authors study the farthest \(g\)-Bregman Voronoi cell of a given site \(s\), denoted by \(Fg T (s)\) and defined as the set of all points that are farther from \(s\) than from any other site with respect to the Bregman distance \(Dg\) associated with \(g\). Characterizations of the sets that can be written as \(Fg T (s)\) for some \(T \subseteq \mathbb{R}^n\) and some \(s \in T\) are provided, too.
Reviewer: Sorin-Mihai Grad (Paris)
MSC:
| 52A20 | Convex sets in \(n\) dimensions (including convex hypersurfaces) |
| 26B25 | Convexity of real functions of several variables, generalizations |
References:
| [1] | Bae, SW. Tight bound for farthest-color Voronoi diagrams of line segments. WALCOM: algorithms and computation, 40-51. Heidelberg: Springer; 2012. (Lecture Notes in Comput. Sci., 7157). · Zbl 1350.68255 |
| [2] | Bae, SW., Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments, Comput Geom, 47, 779-788 (2014) · Zbl 1293.65031 |
| [3] | Bae, SW, Chwa, K -Y. Farthest Voronoi diagrams under travel time metrics (extended abstract). WALCOM: algorithms and computation, 28-39. Heidelberg: Springer; 2012. (Lecture Notes in Comput. Sci., 7157). · Zbl 1350.68256 |
| [4] | Cheong, O.; Everett, H.; Glisse, M., Farthest-polygon Voronoi diagrams, Comput Geom, 44, 234-247 (2011) · Zbl 1210.65055 |
| [5] | de Berg, M, van Kreveld, M, Overmars, M, et al. Computational geometry. Berlin: Springer-Verlag; 1997. (Algorithms and applications). · Zbl 0939.68134 |
| [6] | Dearing, PM; Belotti, P.; Smith, AM., A primal algorithm for the weighted minimum covering ball problem in \(####\), TOP, 24, 466-492 (2016) · Zbl 1462.90125 |
| [7] | Delaunay, B., Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7, 793-800 (1934) · JFM 60.0946.06 |
| [8] | Goberna, MA; Martínez-Legaz, JE; Todorov, MI., On farthest Voronoi cells, Linear Algebra Appl, 583, 306-322 (2019) · Zbl 1429.51008 |
| [9] | Goberna, MA; Martínez-Legaz, JE; Vera de Serio, VN., The Voronoi inverse mapping, Linear Algebra Appl, 504, 248-271 (2016) · Zbl 1381.52028 |
| [10] | Goberna, MA; Rodríguez, MML; Vera de Serio, VN., Voronoi cells via linear inequality systems, Linear Algebra Appl, 436, 2169-2186 (2012) · Zbl 1239.52020 |
| [11] | Preparata, FP, Shamos, MI. Computational geometry. An introduction. New York: Springer-Verlag; 1985. (Texts and Monographs in Computer Science). · Zbl 0575.68059 |
| [12] | Shamos, MI. Computational geometry [Ph.D. Thesis]. Department of Computer Science, Yale University, 1978. Available from University Microfilms, Ann Arbor, MI. |
| [13] | Shamos, MI. The early years of computational geometry – a personal memoir. Advances in discrete and computational geometry (South Hadley, MA, 1996), 313-333, Contemp. Math., 223, Providence (RI): Amer. Math. Soc.; 1999. · Zbl 0916.68173 |
| [14] | Voigt, I.; Weis, S., Polyhedral Voronoi cells, Beiträge Algebra Geom, 51, 587-598 (2010) · Zbl 1342.52021 |
| [15] | Boissonnat, JD; Nielsen, F.; Nock, R., Bregman Voronoi diagrams, Discrete Comput Geom, 44, 281-307 (2010) · Zbl 1201.52020 |
| [16] | Bregman, LM., The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput Math Phys, 7, 200-217 (1967) · Zbl 0186.23807 |
| [17] | Burachik, RS; Martínez-Legaz, JE., On Bregman-type distances for convex functions and maximally monotone operators, Set-Valued Var Anal, 26, 369-384 (2018) · Zbl 06913664 |
| [18] | Censor, Y.; Lent, A., An iterative row-action method for interval convex programming, J Optim Theory Appl, 34, 321-353 (1981) · Zbl 0431.49042 |
| [19] | Rockafellar, RT. Convex analysis. Princeton (NJ): Princeton University Press; 1970. (Princeton Mathematical Series, No. 28). · Zbl 0193.18401 |
| [20] | Fajardo, MD, Goberna, MA, Rodríguez, MML, et al. Even convexity and optimization. handling strict inequalities. Cham: Springer; 2020. (EURO Advanced Tutorials on Operational Research). · Zbl 1462.90002 |
| [21] | Kullback, S.; Leibler, RA., On Information and Sufficiency, Ann Math Stat, 22, 79-86 (1951) · Zbl 0042.38403 |
| [22] | Kulis, B.; Sustik, MA; Dhillon, IS., Low-rank kernel learning with Bregman matrix divergences, J Mach Learn Res, 10, 341-376 (2009) · Zbl 1235.68166 |
| [23] | Zaffaroni, A., Convex coradiant sets with a continuous concave cogauge, J Convex Anal, 15, 325-343 (2008) · Zbl 1148.52002 |
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.
