Varignon frame


The Varignon frame, named after Pierre Varignon, is a mechanical device which can be used to determine an optimal location of a warehouse for the distribution of goods to a set of shops. Optimal means that the sum of the weighted distances of the shops to the warehouse should be minimal. The frame consists of a board with n holes corresponding to the n shops at the locations, n strings are tied together in a knot at one end, the loose ends are passed, one each, through the holes and are attached to weights below the board. If the influence of friction and other odds of the real world are neglected, the strings are long enough to prevent weights being jammed into their holes, and no single weight is so heavy as to pull the knot through the hole and below the table, the knot will take a position of equilibrium. It can be shown, that point is the optimal location which minimizes the weighted sum of distances
The optimization problem is called Weber problem.

Mechanical Problem - Optimization Problem

If the holes have locations and the masses of the weights are then the force acting at the i-th string has the magnitude and direction . Summing up all forces and cancelling the common term one gets the equation
This is a non-linear system for the coordinates of point which can be solved iteratively by the Weiszfeld-algorithm
The connection between equation ' and equation ' is:
Hence Function has at point a local extremum and the Varignon frame provides the optimal location experimentally.

Example

For the following example the points are
and the weights
The coordinates of the optimal solution are and the optimal weighted sum of lengths is. The second picture shows level curves which consist of points of equal but not optimal sums. Level curves can be used for assigning areas, where the weighted sums do not exceed a fixed level. Geometrically they are implicit curves with equations

Special cases n=1 and n=2

  • In case of one gets.
  • In case of and one gets.
  • In case of and point can be any point of the line section . In this case the level curves are confocal ellipses with the points as common foci.

    Weiszfeld-algorithm and a fixpoint problem

Replacing in formula ' vector in the nominator by and in the denominator by and solving the equation for one gets:
which describes an iteration. A suitable starting point is the center of mass with mass in point :
This algorithm is called Weiszfeld-algorithm.
Formula ' can be seen as the iteration formula for determining the fixed point of function
with fixpoint equation
Remark on numerical problems:
The iteration algorithm described here may have numerical problems if point is close to one of the points.