Pairwise Frank-Wolfe for Maximum Inscribed Balls: Enabling Real-Time Geometric Optimization

As a classical convex optimization problem in geometry, computing the maximum inscribed ball (MaxIB) in ultra-high-dimensional polytopes is critical for enabling real-time IoT applications, such as optimal deployment of sensor networks, where polytopes model physical constraints arising from obstacles or coverage boundaries. However, existing methods suffer from the curse of dimensionality, leading to prohibitive computational costs. This paper develops a more efficient approach for computing the (1-\(\epsilon\))-approximate MaxIB in high-dimensional polytopes. To address these challenges, the problem is reformulated with adaptive penalty parameters to enforce strong convexity, enabling linear convergence under the Pairwise Frank–Wolfe (PFW) algorithm. Furthermore, expensive exact line searches are replaced with a backtracking strategy, significantly reducing the per-iteration computational cost. Simulation results demonstrate more than a 12-fold acceleration over existing approximate MaxIB methods across high-dimensional settings, and up to an 80-fold speedup under stringent accuracy requirements, without sacrificing solution quality.