Home > Term: cutting theorem
cutting theorem
For any set H of n hyperplanes in Rk, and any parameter r, 1 ≤ r≤ n, there always exists a (1/r)-cutting of size O(rk). In two dimensions, a (1/r)-cutting of size s is a partition of the plane into s disjoint triangles, some of which are unbounded, such that no triangle in the partition intersects more than n/r lines in H. In Rk, triangles are replaced by simplices. Such a cutting can be computed in O(nrk-1) time.
- Jenis Kata: noun
- Industri / Domain: Sains komputer
- Kategori: Algorithms & data structures
- Government Agency: NIST
0
Penulis
- GeorgeV
- 100% positive feedback