We study the problem of how to breakup many point sets in $\mathbb{R}^d$ into smaller parts using a few splitting (shared) hyperplanes. This problem is related to the classical Ham-Sandwich Theorem. We provide a logarithmic approximation to the optimal solution using the greedy algorithm for submodular optimization.
翻译:我们研究如何使用一些分离(共享)超高平面将许多点分成小部分, 这个问题与经典的 Ham- Sandwich 理论有关。 我们用贪婪的算法来优化亚模块优化, 为最佳解决方案提供一个对数近似值 。