Least Squares Circumcenter of PolygonsIt is well known that the circumcenter of a polygon exists if and only if the polygon is cyclic.I would like to extend the definition of an circumcenter for noncyclic polygons. Namely, let us define the least squares circumcenter as the point A ( x 0 , y 0 ) such that the point A minimizes the sum of the squares of the residuals.Let us consider the case for a noncyclic quadrilateral with vertices P ( x 1 , y 1 ), Q ( x 2 , y 2 ), R ( x 3 , y 3 ), and S ( x 4 , y 4 ). Let us also define the origin O(0,0).How would we solve for the point A in this case? I was thinking of using matrices and solving A T A x ^ = A T b, although any methods are welcome.

Question

Least Squares Circumcenter of PolygonsIt is well known that the circumcenter of a polygon exists if and only if the polygon is cyclic.I would like to extend the definition of an circumcenter for noncyclic polygons. Namely, let us define the least squares circumcenter as the point A   (      x    0    ,      y    0    ) such that the point A minimizes the sum of the squares of the residuals.Let us consider the case for a noncyclic quadrilateral with vertices P   (      x    1    ,      y    1    ), Q  (      x    2    ,      y    2    ), R  (      x    3    ,      y    3    ), and S   (      x    4    ,      y    4    ). Let us also define the origin O(0,0).How would we solve for the point A in this case? I was thinking of using matrices and solving       A          T        A            x      ^        =      A          T        b, although any methods are welcome.

Mario Dorsey · Accepted Answer

Step 1Suppose the polygon has vertices       P    1    ,  …  ,      P    m    ∈            R        n  . The distance       d    i   from a point x to       P    i   is simply       d    i    =  ‖            P      i        −    x        ‖    2  . We would like to minimize the sum of squares of distances. That is, find x solving:      min    x        ∑          i      =      1              m            d    i    2    =      min    x        ∑          i      =      1              m        ‖      P    i    −  x      ‖    2    2  Consider the square of the 2-norm of the block matrix of size   m  n  ×  1 (tall vector),      [                                        P            1                    −          x                                                  P            2                    −          x                                      ⋮                                                  P            m                    −          x                      ]  Step 2The square of the 2-norm of this matrix is exactly       ∑    i        d    i    2  . To see this note that       d    i    2   is the sum of squares of the entries in the vector       P    i    −  x so that       ∑    i        d    i    2   is the sum of squares of the entries in       P    i    −  x for all i.We can rewrite this matrix in the form   b  −  A  x,      [                                        P            1                    −          x                                                  P            2                    −          x                                      ⋮                                                  P            m                    −          x                      ]    =      [                                        P            1                                                            P            2                                                ⋮                                                  P            m                                ]    −      [                            I                                      I                                      ⋮                                      I                      ]    xwhere I is the   n  ×  n identity.To find x we then solve the least squares problem       min    x    ‖  b  −  A  x      ‖    2  .EDIT: to see that this just gives the average of the points, form the normal equations.

Answered question

Answer & Explanation

New Questions in High school geometry