Communications in Information and Systems

Volume 6 (2006)

Number 2

On the Smallest Enclosing Balls

Pages: 137 – 160

DOI: http://dx.doi.org/10.4310/CIS.2006.v6.n2.a3

Authors

Daizhan Cheng

Xiaoming Hu

Clyde Martin

Abstract

In the paper a theoretical analysis is given for the smallest ball that covers a finite number of points $p_1, p_2, \cdots, p_N \in \Bbb R^n$. Several fundamental properties of the smallest enclosing ball are described and proved. Particularly, it is proved that the $k$-circumscribing enclosing ball with smallest $k$ is the smallest enclosing ball, which dramatically reduces a possible large number of computations in the higher dimensional case. General formulas are deduced for calculating circumscribing balls. The difficulty of the closed-form description is discussed. Finally, as an application, the problem of finding a common quadratic Lyapunov function for a set of stable matrices is considered.

Keywords

Smallest enclosing ball; k-dimensional large circle; circumscribing ball

Full Text (PDF format)