Annals of Computer Science and Information Systems, Volume 18

DOI: http://dx.doi.org/10.15439/2019F16

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 157–163 (2019)

Full text

Abstract. Integrating an arbitrary polynomial function f of degree D over a general simplex in dimension n is well-known in the state of the art to be NP-hard when D and n are allowed to vary, but it is time-polynomial when D or n are fixed. This paper presents an efficient algorithm to compute the exact value of this integral. The proposed algorithm has a time-polynomial complexity when D or n are fixed, and it requires a reasonable time when the values of D and n are less than 10 using widely available standard calculators such as desktops.

References

1. V. Baldoni and N. Berline and J. A. De Loera and M. Köppe and M. Vergne, “How to Integrate a Polynomial over a Simplex,” Math. Comput. J., vol. 80, 2011, pp. 297–325.
2. M. E. Dyer and A. M. Frieze, “Frieze, On the complexity of computing the volume of a polyhedron,” SIAM J. Comput. vol. 17, no. 5, 1961, pp. 967-974.
3. J. A. De Loera, J. Rambau, and F. Santos, Triangulations: Structures and algorithms, Book manuscript, 2008.
4. A. H. Stroud, Approximate Calculation of Multiple Integrals. Prentice-Hall, Englewood Cliffs, NJ, 1971.
5. A. Grundmann and H. M. Moller, “Invariant Integration Formulas for the n-Simplex by Combinatorial Methods,” SIAM J. Numer. Anal. vol. 17, no. 5, 1961, pp. 282-290.
6. P. C. Hammer and A. H. Stroud, “Numerical integration over simplexes,” Math Tables other Aids Comput. vol. 10, 1956, pp. 137-139.
7. F. Bernardini, “Integration of polynomials over n-dimensional polyhedra,” Computer-Aided Design vol. 23, no. 11, 1991, pp. 51-58.
8. A. H. Stroud, Approximate Calculation of Multiple Integrals, PrenticeHall, Englewood Cliffs, NJ, 1971. a product of linear forms