Varignon frame

<h2 id="mechanical-problem---optimization-problem">Mechanical Problem - Optimization Problem</h2>

<p>If the holes have locations 
  
    
      
        
          
            x
          
          
            1
          
        
        ,
        …
        ,
        
          
            x
          
          
            n
          
        
      
    
    {\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{n}}
  
 and the masses of the weights are 
  
    
      
        
          m
          
            1
          
        
        ,
        .
        .
        .
        ,
        
          m
          
            n
          
        
      
    
    {\displaystyle m_{1},...,m_{n}}
  
 then the force acting at the i-th string has the magnitude 
  
    
      
        
          m
          
            i
          
        
        ⋅
        g
      
    
    {\displaystyle m_{i}\cdot g}
  
 (
  
    
      
        g
        =
        9.81
        
          m/sec
        
      
    
    {\displaystyle g=9.81{\text{m/sec}}}
  
: constant of gravity) and direction 
  
    
      
        
          
            
              
                
                  
                    x
                  
                  
                    i
                  
                
                −
                
                  v
                
              
              
                ‖
                
                  
                    x
                  
                  
                    i
                  
                
                −
                
                  v
                
                ‖
              
            
          
        
      
    
    {\displaystyle {\tfrac {\mathbf {x} _{i}-\mathbf {v} }{\|\mathbf {x} _{i}-\mathbf {v} \|}}}
  
 (unitvector). Summing up all forces and cancelling the common term 
  
    
      
        g
      
    
    {\displaystyle g}
  
 one gets the equation
</p>
(2):
  
    
      
         
        
          F
        
        (
        
          v
        
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          m
          
            i
          
        
        
          
            
              
                
                  x
                
                
                  i
                
              
              −
              
                v
              
            
            
              ‖
              
                
                  x
                
                
                  i
                
              
              −
              
                v
              
              ‖
            
          
        
        =
        
          0
        
      
    
    {\displaystyle \ \mathbf {F} (\mathbf {v} )=\sum _{i=1}^{n}m_{i}{\frac {\mathbf {x} _{i}-\mathbf {v} }{\|\mathbf {x} _{i}-\mathbf {v} \|}}=\mathbf {0} }
  
.
<p>(At the point of <i>equilibrium</i> the sum of all forces is zero !)
</p><p>This is a <a href="/facts/Non-linear_system/4aYItALC">non-linear system</a> for the coordinates of point 
  
    
      
        
          v
        
      
    
    {\displaystyle \mathbf {v} }
  
 which can be solved iteratively by the <i>Weiszfeld-algorithm</i> (see below)<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p><p>The connection between equation (1) and equation (2) is:
</p>
(3): 
  
    
      
         
        
          F
        
        (
        
          x
        
        )
        =
        ∇
        D
        (
        
          x
        
        )
        =
        
          
            [
            
              
                
                  
                    
                      
                        ∂
                        D
                      
                      
                        ∂
                        x
                      
                    
                  
                
              
              
                
                  
                    
                      
                        ∂
                        D
                      
                      
                        ∂
                        y
                      
                    
                  
                
              
            
            ]
          
        
        .
      
    
    {\displaystyle \ \mathbf {F} (\mathbf {x} )=\nabla D(\mathbf {x} )={\begin{bmatrix}{\frac {\partial D}{\partial x}}\\{\frac {\partial D}{\partial y}}\end{bmatrix}}.}

<p>Hence Function 
  
    
      
        D
      
    
    {\displaystyle D}
  
 has at point 
  
    
      
        
          v
        
      
    
    {\displaystyle \mathbf {v} }
  
 a local extremum and the Varignon frame provides the optimal location experimentally.
</p>

<h2 id="example">Example</h2>
<p>For the following example the points are
</p>

x
          
          
            1
          
        
        =
        (
        0
        ,
        0
        )
        ,
         
        
          
            x
          
          
            2
          
        
        =
        (
        40
        ,
        0
        )
        ,
         
        
          
            x
          
          
            3
          
        
        =
        (
        50
        ,
        40
        )
        ,
      
    
    {\displaystyle \mathbf {x} _{1}=(0,0),\ \mathbf {x} _{2}=(40,0),\ \mathbf {x} _{3}=(50,40),}

x
          
          
            4
          
        
        =
        (
        10
        ,
        50
        )
        ,
         
        
          
            x
          
          
            5
          
        
        =
        (
        −
        10
        ,
        30
        )
      
    
    {\displaystyle \mathbf {x} _{4}=(10,50),\ \mathbf {x} _{5}=(-10,30)}

<p>and the weights 
</p>

m
          
            1
          
        
        =
        10
        ,
        
        
          m
          
            2
          
        
        =
        10
        ,
        
        
          m
          
            3
          
        
        =
        20
        ,
        
        
          m
          
            4
          
        
        =
        10
        ,
        
        
          m
          
            5
          
        
        =
        5
      
    
    {\displaystyle m_{1}=10,\;m_{2}=10,\;m_{3}=20,\;m_{4}=10,\;m_{5}=5}
  
.
<p>The coordinates of the optimal solution (red) are 
  
    
      
        (
        32.5
        ,
        30.1
        )
      
    
    {\displaystyle (32.5,30.1)}
  
 and the optimal weighted sum of lengths is 
  
    
      
        
          L
          
            op
          
        
        =
        1679
      
    
    {\displaystyle L_{\text{op}}=1679}
  
. The second picture shows <a href="/facts/Level_set/JUmNbdNh">level curves</a> 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 <a href="/facts/Implicit_curve/pMFUYp7e">implicit curves</a> with equations 
</p>

D
        (
        
          x
        
        )
        −
        c
        =
        0
        ,
        
        c
        >
        
          L
          
            op
          
        
        
      
    
    {\displaystyle \;D(\mathbf {x} )-c=0,\;c>L_{\text{op}}\;}
  
 (see equation (1)).

<h2 id="special-cases--n1-und-n2">Special cases  n=1 und n=2</h2>
<ul><li>In case of 
  
    
      
        n
        =
        1
      
    
    {\displaystyle n=1}
  
 one gets 
  
    
      
        
          v
        
        =
        
          
            x
          
          
            1
          
        
      
    
    {\displaystyle \mathbf {v} =\mathbf {x} _{1}}
  
.</li>
<li>In case of 
  
    
      
        n
        =
        2
      
    
    {\displaystyle n=2}
  
 and 
  
    
      
        
          m
          
            2
          
        
        >
        
          m
          
            1
          
        
      
    
    {\displaystyle m_{2}>m_{1}}
  
 one gets 
  
    
      
        
          v
        
        =
        
          
            x
          
          
            2
          
        
      
    
    {\displaystyle \mathbf {v} =\mathbf {x} _{2}}
  
.</li>
<li>In case of 
  
    
      
        n
        =
        2
      
    
    {\displaystyle n=2}
  
 and 
  
    
      
        
          m
          
            2
          
        
        =
        
          m
          
            1
          
        
      
    
    {\displaystyle m_{2}=m_{1}}
  
 point 
  
    
      
        
          v
        
      
    
    {\displaystyle \mathbf {v} }
  
 can be any point of the line section 
  
    
      
        
          
            
              
                X
                
                  1
                
              
              
                X
                
                  2
                
              
            
            ¯
          
        
      
    
    {\displaystyle {\overline {X_{1}X_{2}}}}
  
 (see diagram). In this case the level curves  (points with the same  <i>not-optimal</i> sum) are <a href="/facts/Confocal_conic_sections/sNANGYBF">confocal ellipses</a>  with the points 
  
    
      
        
          
            x
          
          
            1
          
        
        ,
        
          
            x
          
          
            2
          
        
      
    
    {\displaystyle \mathbf {x} _{1},\mathbf {x} _{2}}
  
 as common foci.</li></ul>
<h2 id="weiszfeld-algorithm-and-a-fixpoint-problem">Weiszfeld-algorithm and a fixpoint problem</h2>

<p>Replacing in formula (2) vector 
  
    
      
        
          v
        
      
    
    {\displaystyle \mathbf {v} }
  
 in the nominator by 
  
    
      
        
          
            v
          
          
            k
            +
            1
          
        
      
    
    {\displaystyle \mathbf {v} _{k+1}}
  
 and in the denominator by 
  
    
      
        
          
            v
          
          
            k
          
        
      
    
    {\displaystyle \mathbf {v} _{k}}
  
 and solving the equation for 
  
    
      
        
          
            v
          
          
            k
            +
            1
          
        
      
    
    {\displaystyle \mathbf {v} _{k+1}}
  
 one gets:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
(4):
  
    
      
        
        
          
            v
          
          
            k
            +
            1
          
        
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          
            
              
                m
                
                  i
                
              
              
                
                  x
                
                
                  i
                
              
            
            
              ‖
              
                
                  x
                
                
                  i
                
              
              −
              
                
                  v
                
                
                  k
                
              
              ‖
            
          
        
        
          
            /
          
        
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          
            
              m
              
                i
              
            
            
              ‖
              
                
                  x
                
                
                  i
                
              
              −
              
                
                  v
                
                
                  k
                
              
              ‖
            
          
        
      
    
    {\displaystyle \quad \mathbf {v} _{k+1}=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{\|\mathbf {x} _{i}-\mathbf {v} _{k}\|}}{\big /}\sum _{i=1}^{n}{\frac {m_{i}}{\|\mathbf {x} _{i}-\mathbf {v} _{k}\|}}}

<p>which describes an iteration. A suitable starting point is the center of mass with mass 
  
    
      
        
          m
          
            i
          
        
      
    
    {\displaystyle m_{i}}
  
 in point 
  
    
      
        
          
            x
          
          
            i
          
        
      
    
    {\displaystyle \mathbf {x} _{i}}
  
:
</p>

v
          
          
            0
          
        
        =
        
          
            
              
                ∑
                
                  i
                  =
                  1
                
                
                  n
                
              
              
                m
                
                  i
                
              
              
                
                  x
                
                
                  i
                
              
            
            
              
                ∑
                
                  i
                  =
                  1
                
                
                  n
                
              
              
                m
                
                  i
                
              
            
          
        
      
    
    {\displaystyle \mathbf {v} _{0}={\frac {\sum _{i=1}^{n}m_{i}\mathbf {x} _{i}}{\sum _{i=1}^{n}m_{i}}}}
  
.
<p>This algorithm is called  <a href="/facts/Weiszfeld_algorithm/aIQYJaHX">Weiszfeld-algorithm</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p><p>Formula (4) can be seen as the iteration formula for determining the fixed point of function
</p>
(5)
  
    
      
        
        
          G
        
        (
        
          x
        
        )
        =
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          
            
              
                m
                
                  i
                
              
              
                
                  x
                
                
                  i
                
              
            
            
              ‖
              
                
                  x
                
                
                  i
                
              
              −
              
                x
              
              ‖
            
          
        
        
          
            /
          
        
        
          ∑
          
            i
            =
            1
          
          
            n
          
        
        
          
            
              m
              
                i
              
            
            
              ‖
              
                
                  x
                
                
                  i
                
              
              −
              
                x
              
              ‖
            
          
        
      
    
    {\displaystyle \quad \mathbf {G} (\mathbf {x} )=\sum _{i=1}^{n}{\frac {m_{i}\mathbf {x} _{i}}{\|\mathbf {x} _{i}-\mathbf {x} \|}}{\big /}\sum _{i=1}^{n}{\frac {m_{i}}{\|\mathbf {x} _{i}-\mathbf {x} \|}}}

<p>with fixpoint equation
</p>

x
        
        =
        G
        (
        
          x
        
        )
      
    
    {\displaystyle \quad \mathbf {x} =G(\mathbf {x} )}

<p>(see <a href="/facts/Fixed_point_(mathematics)/vVVddTKc">fixed point</a>)
</p><p>Remark on numerical problems:
The iteration algorithm described here may have numerical problems if point  
  
    
      
        
          
            v
          
          
            k
          
        
      
    
    {\displaystyle \mathbf {v} _{k}}
  
 is close to one of the points 
  
    
      
        
          
            x
          
          
            1
          
        
        ,
        .
        .
        .
        
          
            x
          
          
            n
          
        
      
    
    {\displaystyle \mathbf {x} _{1},...\mathbf {x} _{n}}
  
.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Fermat_point/QRvKxfE6">Fermat point</a> (case  
  
    
      
        n
        =
        3
        ,
        
          m
          
            1
          
        
        =
        
          m
          
            2
          
        
        =
        
          m
          
            3
          
        
        =
        1
      
    
    {\displaystyle n=3,m_{1}=m_{2}=m_{3}=1}
  
)</li>
<li><a href="/facts/Varignon%27s_theorem/JDHrd0rT">Varignon's theorem</a></li>
<li><a href="/facts/Geometric_median/aIQYJaHX">geometric median</a></li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.matheprisma.uni-wuppertal.de/Module/StOpt/index.htm?19">MathePrisma Uni Wuppertal: Lösung eines Standort-Problems mit GeoGebra</a></li>
<li><a href="https://mappingaround.in/the-frame-of-varignon/">The Frame of Varignon: Mathematical Treatment</a></li></ul>

<ul><li>Uwe Götze: <i>Risikomanagement</i>, Physica-Verlag HD, 2013, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-57587-7, S. 268</li>
<li>Andrew Wood, Susan Roberts : <i>Economic Geography</i>, Taylor & Francis, 2012, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781136899478, p. 22</li>
<li>H. A. Eiselt, Carl-Louis Sandblom :<i>Operations Research</i>, Springer Berlin Heidelberg, 2010, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9783642103261, p. 239</li>
<li>Robert E. Kuenne: <i>General Equilibrium Economics</i>, Palgrave Macmillan UK, 1992, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781349127528, p. 226</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Z. Drezner, H.W. Hamacher: Facility Location, Springer, 2004, ISBN 3-540-21345-7, p. 7 <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Horst W. Hamacher: Mathematische Lösungsverfahren für planare Standortprobleme, Vieweg+Teubner-Verlag, 2019, ISBN 978-3-663-01968-8, p. 31 <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Karl-Werner Hansmann :Industrielles Management, De Gruyter Verlag, 2014, ISBN 9783486840827, S. 115 <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>see Facility location, p. 9 <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Varignon frame open-in-new

Varignon frame