×

Computing the volume, counting integral points, and exponential sums. (English) Zbl 0774.68054

Summary: We design polynomial-time algorithms for some particular cases of the volume computation problem and the integral points counting problem for convex polytopes. The basic idea is a reduction to the computation of certain exponential sums and integrals. We give elementary proofs of some known identities between these sums and integrals and prove some new identities.

MSC:

68Q25 Analysis of algorithms and problem complexity
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
52A38 Length, area, volume and convex sets (aspects of convex geometry)
11L99 Exponential sums and character sums
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] I. Bárány, Z. Füredi, Computing the volume is difficult,Discrete Comput. Geom.,2(4) (1987), 319-326. · Zbl 0628.68041 · doi:10.1007/BF02187886
[2] A. I. Barvinok, Calculation of exponential integrals (in Russian),Zap. Nauchn. Sem. LOMI, Teoriya Slozhnosti Vychislenii,192(5) (1991), 149-163. · Zbl 0753.65018
[3] M. Brion, Points entiers dans les polyèdres convexes,Ann. Sci. Ècole Norm. Sup (4),21(4) (1988), 653-663. · Zbl 0667.52011
[4] M. Dyer, A. M. Frieze. On the complexity of computing the volume of a polyhedron,SIAM J. Comput.,17(5) (1988), 967-974. · Zbl 0668.68049 · doi:10.1137/0217060
[5] M. Dyer, A. M. Frieze, R. Kannan, A random polynomial time algorithm for approximating the volume of convex bodies,J. Assoc. Comput. Mach.,38(1) (1991), 1-17. · Zbl 0799.68107 · doi:10.1145/102782.102783
[6] M. Grötschel, L. Lovász, A. Schrijver,Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988. · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4
[7] R. Kannan, A. Bachem, Polynomial time algorithms for computing the Smith and Hermite normal forms of an integer matrix,SIAM J. Comput.,8 (1979), 499-507. · Zbl 0446.65015 · doi:10.1137/0208040
[8] L. G. Khachiyan, The problem of calculating the volume of a polyhedron is enumerably hard (in Russian),Uspekhi Mat. Nauk,44(3) (1989), 179-180 (translated inRussian Math. Surveys,44(3) (1989), 199-200). · Zbl 0676.68016
[9] J. Lawrence, Polytope volume computation,Math. Comp.,57(195) (1991), 259-271. · Zbl 0734.52009 · doi:10.1090/S0025-5718-1991-1079024-2
[10] I. G. Macdonald,Symmetric Functions and Hall Polynomials, Clarendon Press, Oxford, 1979. · Zbl 0487.20007
[11] A. N. Podkorytov, Summation of multiple Fourier series over polyhedra (in Russian),Vestnik Leningrad. Univ. Mat. Mekh Astronom., (1) (1980), 51-58. · Zbl 0428.42006
[12] R. P. Stanley,Enumerative Combinatorics, vol. 1, Wadsworth & Brooks/Cole, Monterey, California, 1986. · Zbl 0608.05001 · doi:10.1007/978-1-4615-9763-6
[13] A. N. Varchenko, Combinatorics and topology of the disposition of affine hyperplanes in real space (in Russian),Funktsional. Anal. i Prilozhen.,21(1) (1987), 11-22 (translated inFunctional Anal. Appl.,21(1) (1987), 9-19). · Zbl 0615.52005 · doi:10.1007/BF01077981
[14] A. N. Varchenko, I. M. Gel’fand, On Heaviside functions of a configuration of hyperplanes (in Russian),Funktsional. Anal. i Prilozhen.,21(4) (1987), 1-18 (translated inFunctional Anal. Appl.,21(4) (1987), 255-270). · Zbl 0647.32013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.