# Closest Farthest Widest
## 1 Introduction  
Let \(S\) be a compact convex set and \(\mathbf{p}\) any external or internal point. This paper investigates algorithms for computing the two functions \(\operatorname{far}_{S}(\mathbf{p})=\max_{x\in S}\|\mathbf{x}-\mathbf{p}\|\) and \(\operatorname{diam}(S)=\max_{(\mathbf{x},\mathbf{y})\in S\times S}\|\mathbf{x}-\mathbf{y}\|\). The first is the farthest distance from \(\mathbf{p}\) to \(\mathbf{x}\in S\), and the second is the diameter of \(S\). Both objective functions are convex and Lipschitz under the Euclidean norm, the first with constant \(1\) and the second with constant \(2\). Furthermore, if \(S\) is merely bounded, and \(\operatorname{conv}(S)\) denotes its closed convex hull, and \(\operatorname{ext}(S)\) denotes the extreme points of \(\operatorname{conv}(S)\), then  
\[\operatorname{far}_{S}(\mathbf{p}) = \operatorname{far}_{\operatorname{conv}(S)}(\mathbf{p})\quad= \operatorname{far}_{\operatorname{ext}(S)}(\mathbf{p})\] \[\operatorname{diam}(S) = \operatorname{diam}[\operatorname{conv}(S)]\quad= \operatorname{diam}[\operatorname{ext}(S)\times\operatorname{ext}(S)].\]  
The fact that \(\operatorname{conv}(S)\) is compact is crucial in the reaching these conclusions. Thus, without loss of generality, we can assume that \(S\) is a compact convex set. All boundary points \(S\) are extreme points when \(S\) is strictly convex [1, 2]. If \(S\) is the convex hull of a finite cloud of points \(\{\mathbf{x}_{1},\dots,\mathbf{x}_{m}\}\), then \(\operatorname{far}_{S}(\mathbf{p})\) can be found by identifying the point \(\mathbf{x}_{i}\) that maximizes \(\|\mathbf{x}_{i}-\mathbf{p}\|\). For a ball \(S\) and a point \(\mathbf{y}\
ot\in S\), \(\operatorname{far}_{S}(\mathbf{p})\) is found by projecting \(\mathbf{y}\) onto \(S\) and then extending the line through \(\mathbf{y}\) and its projection \(\mathbf{z}\) to the antipodal point of \(\mathbf{z}\). If the set \(S\) is a Cartesian product, then calculation of \(\operatorname{far}_{S}(\mathbf{p})\) and \(\operatorname{diam}(S)\) reduce to easy lower-dimensional problems. Many diameters are known. For a ball, ellipsoid \(\{\mathbf{x}:\frac{1}{2}\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\leq r\}\), rectangle \([\mathbf{a},\mathbf{b}]\), probability simplex, and \(\ell_{1}\) unit ball, the diameter is, respectively, twice its radius, \(\sqrt{8r\lambda_{\min}^{-1}}\|\mathbf{a}-\mathbf{b}\|,\sqrt{2}\), and \(2\), where \(\lambda_{\min}\) is the smallest eigenvalue of the positive definite matrix \(\mathbf{A}\)[3]. The distance function \(\operatorname{dist}(\mathbf{p},S)=\min_{x\in S}\|\mathbf{x}-\mathbf{p}\|\) is extremely well studied [4, 5, 6, 7]. The unique point where the minimum is attained is the projection \(P_{S}(\mathbf{p})\) of \(\mathbf{p}\) onto \(S\)Many projection operators are known [4; 6; 7; 8; 9]. The web sites [10; 11] provide Julia, Python, and Matlab implementations of the most commonly encountered projection operators. Projection onto a convex sublevel set \(S=\{\boldsymbol{x}:g(\boldsymbol{x})\leq 0\}\) is often more computationally demanding than other projection problems. For the special case when the proximal operator \(\operatorname{prox}_{\lambda g}(\boldsymbol{y})=\operatorname{argmin}_{ \boldsymbol{x}}\left[\lambda g(\boldsymbol{x})+\frac{1}{2}\|\boldsymbol{y}- \boldsymbol{x}\|^{2}\right]\) is known for all \(\lambda>0\), one can solve the projection problem by bisection [12]. Bisection also turns out to be an attractive strategy for computing \(\operatorname{far}_{S}(\boldsymbol{p})\) and \(\operatorname{diam}(S)\) for sublevel sets. The corresponding operators for \(\operatorname{far}_{S}(\boldsymbol{p})\) and \(\operatorname{diam}(S)\) can be multi-valued. Finding them is more challenging because the underlying optimization problem is no longer convex. The current paper proposes two algorithms for each problem. These algorithms are not infallible. They are ascent algorithms, so they tend to find local maxima.