A geometric inequality and the complexity of computing volume |
| |
| Authors: | G Elekes |
| |
| Institution: | (1) Mathematical Institute, Eötvös Loránd University, Muzeum krt. 6-8, H-1088 Budapest, Hungary |
| |
| Abstract: | The volume of the convex hull of anym points of ann-dimensional ball with volumeV is at mostV·m/2
n
. This implies that no polynomial time algorithm can compute the volume of a convex set (given by an oracle) with less than exponential relative error. A lower bound on the complexity of computing width can also be deduced.Dedicated to my teacher Kõváry Károly |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
