Effective Neural Approximations for Geometric Optimization Problems

Neural networks offer a promising data-driven approach to tackle computationally challenging optimization problems. In this work, we introduce neural approximation frameworks for a family of geometric "extent measure" problems, including shape-fitting descriptors (e.g. minimum enclosing ball or annulus). Central to our approach is the alignment of our neural model with a new variant of the classical ε-kernel technique from computational geometry. In particular, we develop a new relaxed-ε-kernel theory that maintains the approximation guarantees of the classical ε-kernels but with the crucial benefit that it can be implemented with bounded model complexity (i.e, constant number of parameters) by the simple SumFormer neural network. This leads to a simple neural model that approximate quantities such as the directional width of any input point set and empirically shows good out-of-distribution generalization. Many geometric extent measures, such as the minimum enclosing spherical shell, cannot be directly captured by ε-kernels. To this end, we show that an encode-process-decode framework with our kernel-approximating NN used as the "process" module can approximate such extent measures, again, with bounded model complexity where parameters scale only with the approximation error ε and not the size of the input set. Empirical results on diverse point-cloud datasets demonstrate the practical performance of our models.