polygon_average

polygon_average, an Octave code which demonstrates a process of repeatedly averaging and normalizing the vertices of a polygon, illustrating a property of the power method.

The process can be analyzed in terms of the power method, and the eigenvalues of the matrix that carries out the averaging process.

A polygon is represented by a list of N vertices. An averaging step involves:

• replacing each vertex by the average of its two neighbors,
• shifting these vertices to have centroid 0;
• scaling the X and Y coordinates separately so that the max-norms of the X and Y coordinate vectors are both 1.

If the averaging process is carried out recursively, the resulting polygon rapidly converges to an ellipse at a 45 degree tilt.

The direction of the tilt, and the ratio between the major and minor axis lengths, vary depending on the initial polygon.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

polygon_average is available in a MATLAB version and an Octave version.

Related Data and Programs:

polygon_average_test

power_method, an Octave code which carries out the power method for finding a dominant eigenvalue and its eigenvector.

Reference:

1. Charles Van Loan, Daisy Fan,
   Insight Through Computing,
   SIAM Publishing, 2010,
   ISBN: 978-0-898716-91-7
2. Adam Elmachtoub, Charles Van Loan,
   From Random Polygon to Ellipse: An Eigenanalysis,
   SIAM Review,
   Volume 52, Number 1, March 2010, pages 151-170.

Source Code:

• polygon_average.m, carries out one step of the averaging process.