APPROXIMATING THE VOLUME OF CONVEX-BODIES

Authors
BETKE U HENK M
Citation
U. Betke et M. Henk, APPROXIMATING THE VOLUME OF CONVEX-BODIES, Discrete & computational geometry, 10(1), 1993, pp. 15-21
Citations number
9
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, Pure","Computer Applications & Cybernetics",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
10
Issue
1
Year of publication
1993
Pages
15 - 21
Database
ISI
SICI code
0179-5376(1993)10:1<15:ATVOC>2.0.ZU;2-#
Abstract
It is a well-known fact that for every polynomial-time algorithm which gives an upper bound V(K)BAR and a lower bound V(K)underbar for the v olume of a convex set K subset-of E(d) given by an oracle, the ratio V (K)BAR/V(K)underbar is at least (cd/log d)d. Here we describe an algor ithm which gives, for epsilon > 0, in polynomial time, an upper and lo wer bound with the property V(K)BAR/V(K)underbar less-than-or-equal-to d! (1 + epsilon)d.