9860

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:
,
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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+