A Discrete Green's Theorem
Generally speaking, Green's theorem states the connection between the line integral of two vector fields on an edge of a domain and the double integral of a linear combination of the vector fields' partial derivatives over the interior of the domain. The discrete Green's theorem resembles Green's theorem in the sense that it also states the connection between (discrete) summation of values of a function over a domain's edge, and the double integral of a linear combination of the function's derivative over the interior of the domain. The theorem allows us to efficiently calculate a function's double integral in a "generalized rectangular domain", that is, a domain that consists of a union of rectangles with sides parallel to the axes. The formulation of the theorem is as follows: let be an integrable function, and suppose that its local antiderivative, , was pre-calculated. Then in order to calculate the function's double integral over a generalized rectangular domain , only a few arithmetical operations are required:[more]
where the summation is over the domain's corners and is a parameter that is determined according to the corner's type (see the Details section).
In the above graph, we are given an arbitrary integrable function and a domain over which it is defined, for which the discrete Green's theorem states that
In this Demonstration, you can choose any of the vertices , , , , , , , , for the linear combination; this will help to give an intuitive understanding of the formula. The darker the color of a region (green or red), the more times it is being covered by the linear combination's matching double integrals.[less]
Snapshot 1: all the vertices participate in the linear combination, hence (and as the theorem assures) the given domain is covered once
Snapshot 2: the only vertices chosen in the linear combination are and ; regions that are covered twice are colored in darker green
Snapshot 3: the only vertices chosen in the linear combination are and ; since the coefficient of in the linear combination is , the region that is common to the vertices' matching double integral is colored in light red, since
For the reader's convenience, the classification of corners types which allows the determination of the parameter from the formulation of the theorem is available at this link.
Ever since the early 1980s, computer scientists have been using discrete versions of Green's and Stokes's theorems. These theorems were shown to provide a tremendous computational gain, since they fit the needs of discrete geometry researchers precisely due to their discrete nature. The discrete Green's theorem is a natural generalization to the summed area table algorithm.
It was suggested that the discrete Green's theorem is actually derived from a differently defined calculus, namely the "calculus of detachment". That is, a more rigorous approach to the definition of the parameter is obtained by a simplification of the derivative. Thus, the main operator of this theory is defined by a mixture of the discrete and continuous to form a semi-discrete version of the familiar derivative. This approach is therefore more suitable for computers (in order to save computation time), and the simplicity of the definition allows further research in other areas of classical analysis. A basic and not very comprehensive video introduction to this theory is available, and a preprint is also available. Among others, an extension of the discrete Green's theorem to more general domains is suggested in the preprint.
This Demonstration's version of the discrete Green's theorem was introduced in
X. Wang, G. Doretto, T. Sebastian, J. Rittscher, and P. Tu, "Shape and Appearance Context Modeling," in Proceedings of the IEEE 11th International Conference on Computer Vision, 2007 pp. 1–8.