Minimum enclosing Bregman balls made easy
2026-07-27 • Information Theory
Information TheoryComputational Geometry
AI summaryⓘ
The authors revisit how to find the smallest enclosing Bregman ball (a kind of generalized circle) for a set of points. They show that this problem can be transformed into finding a similar ball for weighted points using power distance. They provide an efficient algorithm based on the Frank-Wolfe method that approximates this ball well. Additionally, they reinterpret earlier geometric transformations related to Bregman diagrams as classical paraboloid liftings, linking Bregman ball centers to farthest Voronoi and power diagrams.
Bregman ballminimum enclosing ballpower distanceFrank-Wolfe algorithmapproximation algorithmdual gradient spaceBregman Voronoi diagramparaboloid liftingfarthest Voronoi diagrampower diagram
Authors
Frank Nielsen
Abstract
In this work, we revisit the problem of computing minimum enclosing Bregman balls (Bregman MEBs) of finite sets of parameters. First, we show that Bregman MEBs are equivalent to MEBs of corresponding weighted point sets with respect to the power distance. We then report an efficient Frank--Wolfe $(1+ε)$-approximation algorithm for computing power MEBs, for any $ε>0$. This power MEB approximation algorithm coincides with the Bregman MEB approximation algorithm of Nock and Nielsen (2005) when expressed in the dual gradient space. Finally, we show that the Bregman potential lifting transforms used to construct Bregman Voronoi diagrams can be reinterpreted as the classical paraboloid lifting transform applied to corresponding weighted point sets. In particular, Bregman MEB circumcenters lie on the farthest Bregman Voronoi diagrams or equivalently on the corresponding farthest power diagrams.