首页> 外文会议>Algorithms and computation >Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects
【24h】

Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects

机译:逼近高维几何对象的并集和相交的体积

获取原文
获取原文并翻译 | 示例

摘要

We consider the computation of the volume of the union of high-dimensional geometric objects. While showing that this problem is #P-hard already for very simple bodies (i.e., axis-parallel boxes), we give a fast FPRAS for all objects where one can: (1) test whether a given point lies inside the object, (2) sample a point uniformly, (3) calculate the volume of the object in polynomial time. All three oracles can be weak, that is, just approximate. This implies that Klee's measure problem and the hypervolume indicator can be approximated efficiently even though they are #P-hard and hence cannot be solved exactly in time polynomial in the number of dimensions unless P = NP. Our algorithm also allows to approximate efficiently the volume of the union of convex bodies given by weak membership oracles.rnFor the analogous problem of the intersection of high-dimensional geometric objects we prove #P-hardness for boxes and show that there is no multiplicative polynomial-time 2~(d1-ε) -approximation for certain boxes unless NP = BPP, but give a simple additive polynomial-time ε-approximation.
机译:我们考虑计算高维几何对象的并集体积。尽管已经证明对于非常简单的物体(即,平行轴的盒子)来说,这个问题已经是#P难题了,但我们为所有对象提供了一种快速的FPRAS,其中: 2)均匀采样一个点,(3)以多项式时间计算对象的体积。这三个预言都可能是弱的,即只是近似值。这意味着即使Klee的度量问题和超量指标是#P-hard的,它们也可以有效地近似,因此除非P = NP,否则无法在维数上精确地按时间多项式求解。我们的算法还允许有效地近似由弱隶属度预言给出的凸体并集的体积。对于类似高维几何对象相交的问题,我们证明了框的#P硬度,并表明没有乘法多项式除非NP = BPP,否则某些盒的时间2〜(d1-ε)-逼近,但给出简单的加法多项式时间ε-逼近。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号