A sweep-plane algorithm for computing the volume of polyhedra represented in boolean form
A sweep-plane algorithm for computing the volume of polyhedra represented in boolean form
复制标题
用于计算以布尔形式表示的多面体体积的扫描平面算法
DOI：
10.1016/0024-3795(83)80008-1
复制
发表时间：
1983
影响因子：
1.1
通讯作者：
Alexander M. Ostrowski
中科院分区：
文献类型：
--
作者：
H. Bieri;W. Nef;Alexander M. Ostrowski
本文提出了一种计算有界多面体P <$Rd的d维体积V（P）的算法polvol。证明了V（P）是由P在其所有顶点的局部性质决定的。因此，我们的方法包括让一个超平面“扫描”通过R d，收集P的每个顶点ak处可用的局部信息。这导致每个ak对体积的附加贡献，这些贡献的总和是V（P）。假设P以布尔形式表示，如[13]中所述。
We present an algorithm polvol for the computation of the d-dimensional volume V (P) of a bounded polyhedron P⊂ R d. It is shown that V (P) is determined by the local properties of P at all its vertices. So our method consists in letting a hyperplane “sweep” through R d, collecting the local information available at every vertex a k of P. This leads to an additive contribution to the volume from every a k, the sum of these contributions being V (P). It is assumed that P is represented in Boolean form as described in [13].