寻找 $n$ 个点中最大的空轴对齐盒子
给定 $n$ 个带权点(正面或负面)在 $d$ 个维度中,如何找到包含权重点的总和最大的轴对齐箱子?本文提供一种新的匹配条件的下限,基于这个假设 -All-Pairs Shortest Paths 问题和 Max-Weight k-Clique 问题的最佳已知算法是基本最优的。
Feb, 2016
本论文提出了一种多项式时间复杂度下可以近似求解凸包中体积最大值的算法,近似比可以达到 $O (log d)^{d/2}$。此外,本文也展示了此问题的不可近似性,除非 $P=NP$。类似的结果也适用于矩阵行列式的最大值问题。
Jun, 2014
本研究探讨高维几何对象的求并集体积问题。本文给出了一个快速的 FPRAS 算法,可以有效地逼近 Klee's measure problem 和 hypervolume indicator,并能够逼近由弱成员资格证明给出的凸体的并集体积。同时,作者还探讨了高维几何对象的交集计算问题,并证明了其 #P 难度。
Sep, 2008
本研究提供了确定性逼近算法来解决最大体积 $j$-simplex 问题,同时给出了这个问题的近似比。我们通过将 $D$- 最优设计问题的解进行四舍五入得到了我们的近似算法,并且给出了行列式的有限逆原理的简洁证明。
Nov, 2014
研究拟合 n 个高斯随机向量到以原点为中心的椭球体边界问题,证明了它在 n 与 d 趋近于无穷大的情况下具有尖锐的可行性转变,并使用 Bartl&Mendelson 的关键结果和矩阵专业性质得出了当 n ≤ d²/C 时 (此处 C>0 是一个常数),该问题是可行的且概率高。
Jul, 2023
提出了一种利用轴对齐超矩形进行支配区域划分的新方法来计算超体积指标,包括一个非增量算法和一个增量算法。虽然其理论复杂度受到了分区复杂度的下界限制,但该方法在实践中具有高效性。此外,证明了 WFG 算法的最坏情况下的复杂度的改进上限和下限。
Oct, 2015
本研究提出一种基于 Chebyshev cooling 并利用量子随机游走技术的量子算法,用于估算多维凸包的体积,比已知的经典算法要更快,同时还证明了量子算法所需的查询次数。
Aug, 2019
在 d 维空间中,从标准正态分布中选择 n 个独立的随机点,得到凸包 K_n,称为高斯随机多面体。我们证明,K_n 的体积和面数满足中心极限定理,解决了该领域一个著名的猜想。
Oct, 2006