# Closest Farthest Widest
## 1 Introduction
Convex hull algorithms can be harnessed to solve the farthest and diameter problems for finite point clouds in dimensions greater than 3 [13; 14]. To our knowledge, these are the only competitive algorithms in common use in higher dimensions. Hence, any progress in solving these two fundamental geometric problems should be welcome. Unfortunately, convex hull algorithms scale poorly in high dimensions. For \(n\) points in \(\mathbb{R}^{p}\), an \(n\)-vertex polytope can have as many as \(O(n^{\lfloor\frac{p}{2}\rfloor})\) facets [15]. This translates into a worst-case computational computational complexity of \(O(n^{\lfloor\frac{p}{2}\rfloor})\) for traditional convex hull algorithms. It is true that once the \(m\) extreme points are extracted from the convex hull, the farthest and diameter problems require computing just \(m\) and \(m^{2}\) distances, respectively. In contrast, we circumvent the convex hull problem entirely and attack the farthest and diameter problems directly. Thus, we easily handle problems in dimension \(p=1000\). Given the naturalness of the farthest and diameter problems, a few comments should suffice to motivate each. The minimum enclosing ball problem reduces to find  
\[\operatorname{argmin}_{c\in S}\max_{\boldsymbol{x}\in S}\| \boldsymbol{x}-\boldsymbol{c}\| = \operatorname{argmin}_{c\in S}\operatorname{far}_{S}(\boldsymbol{c}).\]  
The solution point \(\boldsymbol{c}\) is called the Chebyshev center. Article [16] explains the pertinence to statistics. As for the diameter problem, convergence estimates for the Frank-Wolfe method of optimization depend on the squared diameter of the underlying set [17; 18]. In general for an \(L\)-Lipschitz function \(f(\boldsymbol{x})\), the inequality \(|f(\boldsymbol{x})|\leq|f(\boldsymbol{y})|+L\operatorname{diam}(S)\) bounds objective values. Bounding objective values is crucial in deriving complexity estimates for optimization algorithms such as projected gradient descent. If instead \(\
abla f(\boldsymbol{x})\) possesses an \(L\)-Lipschitz gradient, then the bound  
\[\|\
abla f(\boldsymbol{x})-\
abla f(\boldsymbol{y})\| \leq L\operatorname{diam}(S)\]  
is available for proving convergence to a stationary point. The diameter of a set also plays a crucial role in estimating the concentration of probability measures [19]. Finally, let us draw attention to a theorem of [PERSON] to the effect that the radius \(r\) of the minimum enclosing ball problem satisfies \(r\leq\operatorname{diam}(S)\sqrt{\frac{p}{2(p+1)}}\) for \(S\subset\mathbb{R}^{p}\)[20]. Our algorithms are minorization-maximization (MM) algorithms [7; 21]. Such algorithms depend on a surrogate function that minorizes the original objective \(f(\boldsymbol{x})\) around the current iterate \(\boldsymbol{x}_{n}\) in the sense of satisfying the tangency condition \(g(\boldsymbol{x}_{n}\mid\boldsymbol{x}_{n})=f(\boldsymbol{x}_{n})\) and the domination condition \(g(\boldsymbol{x}\mid\boldsymbol{x}_{n})\leq f(\boldsymbol{x})\) for all \(\boldsymbol{x}\). The surrogate balances two goals, hugging the objective tightly and simplifying maximization. Maximizing the surrogate produces the next iterate \(\boldsymbol{x}_{n+1}\) and drives the objective uphill because  
\[f(\boldsymbol{x}_{n+1}) \geq g(\boldsymbol{x}_{n+1}\mid\boldsymbol{x}_{n}) \geq g(\boldsymbol{x}_{n}\mid\boldsymbol{x}_{n}) = f(\boldsymbol{x}_{n}).\]  
In minimization, the surrogate majorizes the objective and is instead minimized. The tangency condition remains the same, but now the domination condition \(g(\boldsymbol{x}\mid\boldsymbol{x}_{n})\geq f(\boldsymbol{x})\) is reversed. The acronym MM also applies to majorization-minimization. The celebrated EM (expectation-maximization) principle for maximum likelihood estimation with missing data [22] is a special case of minorization-maximization. In the EM setting, Jensen's inequality supplies the surrogate as the expectation of the complete data log-likelihood conditional on the observed data.