Least Squares Circumcenter of Polygons












0












$begingroup$


It 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^mathsf{T}A hat{x} = A^mathsf{T}b$, although any methods are welcome.






linear-algebra geometry least-squares







share|cite|improve this question











$endgroup$












  • $begingroup$
    Are you asking about how to set up the least squares problem, or how to solve it once you have it? Forming and solving the normal equations directly is numerically unstable.
    $endgroup$
    – tch
    Dec 26 '18 at 18:17










  • $begingroup$
    @TylerChen My question is asking for the least squares solution to the circumcenter, in closed form. I don't have a background in least squares but any methods are acceptable as long as they yield the correct answer. Thanks.
    $endgroup$
    – pacosta
    Dec 26 '18 at 18:41












  • $begingroup$
    Thanks for the update! When you say residual, do you mean the difference between he center point and vertices?
    $endgroup$
    – tch
    Dec 26 '18 at 18:44












  • $begingroup$
    Not sure I understand. Do you want to minimize the sum of the distances to the vertices? For a triangle, that's the Fermat point, not the incenter. No "least squares" involved...you aren't fitting anything. Did you want something else?
    $endgroup$
    – lulu
    Dec 26 '18 at 19:13












  • $begingroup$
    Also: you appear to be alternating between references to the incenter and the circumcenter. Which is it you are trying to generalize? Note that the circumcenter of a triangle can be very far from the vertices...
    $endgroup$
    – lulu
    Dec 26 '18 at 19:15
















0












$begingroup$


It 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^mathsf{T}A hat{x} = A^mathsf{T}b$, although any methods are welcome.






linear-algebra geometry least-squares







share|cite|improve this question











$endgroup$












  • $begingroup$
    Are you asking about how to set up the least squares problem, or how to solve it once you have it? Forming and solving the normal equations directly is numerically unstable.
    $endgroup$
    – tch
    Dec 26 '18 at 18:17










  • $begingroup$
    @TylerChen My question is asking for the least squares solution to the circumcenter, in closed form. I don't have a background in least squares but any methods are acceptable as long as they yield the correct answer. Thanks.
    $endgroup$
    – pacosta
    Dec 26 '18 at 18:41












  • $begingroup$
    Thanks for the update! When you say residual, do you mean the difference between he center point and vertices?
    $endgroup$
    – tch
    Dec 26 '18 at 18:44












  • $begingroup$
    Not sure I understand. Do you want to minimize the sum of the distances to the vertices? For a triangle, that's the Fermat point, not the incenter. No "least squares" involved...you aren't fitting anything. Did you want something else?
    $endgroup$
    – lulu
    Dec 26 '18 at 19:13












  • $begingroup$
    Also: you appear to be alternating between references to the incenter and the circumcenter. Which is it you are trying to generalize? Note that the circumcenter of a triangle can be very far from the vertices...
    $endgroup$
    – lulu
    Dec 26 '18 at 19:15














0












0








0





$begingroup$


It 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^mathsf{T}A hat{x} = A^mathsf{T}b$, although any methods are welcome.






linear-algebra geometry least-squares







share|cite|improve this question











$endgroup$




It 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^mathsf{T}A hat{x} = A^mathsf{T}b$, although any methods are welcome.






linear-algebra geometry least-squares




linear-algebra geometry least-squares






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 26 '18 at 21:10







pacosta

















asked Dec 26 '18 at 17:52









pacostapacosta

1535




1535












  • $begingroup$
    Are you asking about how to set up the least squares problem, or how to solve it once you have it? Forming and solving the normal equations directly is numerically unstable.
    $endgroup$
    – tch
    Dec 26 '18 at 18:17










  • $begingroup$
    @TylerChen My question is asking for the least squares solution to the circumcenter, in closed form. I don't have a background in least squares but any methods are acceptable as long as they yield the correct answer. Thanks.
    $endgroup$
    – pacosta
    Dec 26 '18 at 18:41












  • $begingroup$
    Thanks for the update! When you say residual, do you mean the difference between he center point and vertices?
    $endgroup$
    – tch
    Dec 26 '18 at 18:44












  • $begingroup$
    Not sure I understand. Do you want to minimize the sum of the distances to the vertices? For a triangle, that's the Fermat point, not the incenter. No "least squares" involved...you aren't fitting anything. Did you want something else?
    $endgroup$
    – lulu
    Dec 26 '18 at 19:13












  • $begingroup$
    Also: you appear to be alternating between references to the incenter and the circumcenter. Which is it you are trying to generalize? Note that the circumcenter of a triangle can be very far from the vertices...
    $endgroup$
    – lulu
    Dec 26 '18 at 19:15


















  • $begingroup$
    Are you asking about how to set up the least squares problem, or how to solve it once you have it? Forming and solving the normal equations directly is numerically unstable.
    $endgroup$
    – tch
    Dec 26 '18 at 18:17










  • $begingroup$
    @TylerChen My question is asking for the least squares solution to the circumcenter, in closed form. I don't have a background in least squares but any methods are acceptable as long as they yield the correct answer. Thanks.
    $endgroup$
    – pacosta
    Dec 26 '18 at 18:41












  • $begingroup$
    Thanks for the update! When you say residual, do you mean the difference between he center point and vertices?
    $endgroup$
    – tch
    Dec 26 '18 at 18:44












  • $begingroup$
    Not sure I understand. Do you want to minimize the sum of the distances to the vertices? For a triangle, that's the Fermat point, not the incenter. No "least squares" involved...you aren't fitting anything. Did you want something else?
    $endgroup$
    – lulu
    Dec 26 '18 at 19:13












  • $begingroup$
    Also: you appear to be alternating between references to the incenter and the circumcenter. Which is it you are trying to generalize? Note that the circumcenter of a triangle can be very far from the vertices...
    $endgroup$
    – lulu
    Dec 26 '18 at 19:15
















$begingroup$
Are you asking about how to set up the least squares problem, or how to solve it once you have it? Forming and solving the normal equations directly is numerically unstable.
$endgroup$
– tch
Dec 26 '18 at 18:17




$begingroup$
Are you asking about how to set up the least squares problem, or how to solve it once you have it? Forming and solving the normal equations directly is numerically unstable.
$endgroup$
– tch
Dec 26 '18 at 18:17












$begingroup$
@TylerChen My question is asking for the least squares solution to the circumcenter, in closed form. I don't have a background in least squares but any methods are acceptable as long as they yield the correct answer. Thanks.
$endgroup$
– pacosta
Dec 26 '18 at 18:41






$begingroup$
@TylerChen My question is asking for the least squares solution to the circumcenter, in closed form. I don't have a background in least squares but any methods are acceptable as long as they yield the correct answer. Thanks.
$endgroup$
– pacosta
Dec 26 '18 at 18:41














$begingroup$
Thanks for the update! When you say residual, do you mean the difference between he center point and vertices?
$endgroup$
– tch
Dec 26 '18 at 18:44






$begingroup$
Thanks for the update! When you say residual, do you mean the difference between he center point and vertices?
$endgroup$
– tch
Dec 26 '18 at 18:44














$begingroup$
Not sure I understand. Do you want to minimize the sum of the distances to the vertices? For a triangle, that's the Fermat point, not the incenter. No "least squares" involved...you aren't fitting anything. Did you want something else?
$endgroup$
– lulu
Dec 26 '18 at 19:13






$begingroup$
Not sure I understand. Do you want to minimize the sum of the distances to the vertices? For a triangle, that's the Fermat point, not the incenter. No "least squares" involved...you aren't fitting anything. Did you want something else?
$endgroup$
– lulu
Dec 26 '18 at 19:13














$begingroup$
Also: you appear to be alternating between references to the incenter and the circumcenter. Which is it you are trying to generalize? Note that the circumcenter of a triangle can be very far from the vertices...
$endgroup$
– lulu
Dec 26 '18 at 19:15




$begingroup$
Also: you appear to be alternating between references to the incenter and the circumcenter. Which is it you are trying to generalize? Note that the circumcenter of a triangle can be very far from the vertices...
$endgroup$
– lulu
Dec 26 '18 at 19:15










1 Answer
1






active

oldest

votes


















0












$begingroup$

Suppose the polygon has vertices $P_1,ldots, P_m inmathbb{R}^n$. The distance $d_i$ from a point $x$ to $P_i$ is simply $d_i = lVert{P_i-x}rVert_2$. We would like to minimize the sum of squares of distances. That is, find $x$ solving:
$$
min_x sum_{i=1}^{m} d_i^2
= min_x sum_{i=1}^{m} lVert P_i-xrVert_2^2
$$



Consider the square of the 2-norm of the block matrix of size $mntimes 1$ (tall vector),
$$
begin{bmatrix}
P_1-x \
P_2-x \
vdots \
P_m-x
end{bmatrix}
$$



The square of the 2-norm of this matrix is exactly $sum_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 $sum_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-Ax$,
$$
begin{bmatrix}
P_1-x \
P_2-x \
vdots \
P_m-x
end{bmatrix}
=
begin{bmatrix}
P_1\
P_2 \
vdots \
P_m
end{bmatrix}
-
begin{bmatrix}
I \
I \
vdots \
I
end{bmatrix}
x
$$
where $I$ is the $ntimes n$ identity.



To find $x$ we then solve the least squares problem $min_x lVert b-Ax rVert_2$.






share|cite|improve this answer









$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053149%2fleast-squares-circumcenter-of-polygons%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    Suppose the polygon has vertices $P_1,ldots, P_m inmathbb{R}^n$. The distance $d_i$ from a point $x$ to $P_i$ is simply $d_i = lVert{P_i-x}rVert_2$. We would like to minimize the sum of squares of distances. That is, find $x$ solving:
    $$
    min_x sum_{i=1}^{m} d_i^2
    = min_x sum_{i=1}^{m} lVert P_i-xrVert_2^2
    $$



    Consider the square of the 2-norm of the block matrix of size $mntimes 1$ (tall vector),
    $$
    begin{bmatrix}
    P_1-x \
    P_2-x \
    vdots \
    P_m-x
    end{bmatrix}
    $$



    The square of the 2-norm of this matrix is exactly $sum_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 $sum_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-Ax$,
    $$
    begin{bmatrix}
    P_1-x \
    P_2-x \
    vdots \
    P_m-x
    end{bmatrix}
    =
    begin{bmatrix}
    P_1\
    P_2 \
    vdots \
    P_m
    end{bmatrix}
    -
    begin{bmatrix}
    I \
    I \
    vdots \
    I
    end{bmatrix}
    x
    $$
    where $I$ is the $ntimes n$ identity.



    To find $x$ we then solve the least squares problem $min_x lVert b-Ax rVert_2$.






    share|cite|improve this answer









    $endgroup$


















      0












      $begingroup$

      Suppose the polygon has vertices $P_1,ldots, P_m inmathbb{R}^n$. The distance $d_i$ from a point $x$ to $P_i$ is simply $d_i = lVert{P_i-x}rVert_2$. We would like to minimize the sum of squares of distances. That is, find $x$ solving:
      $$
      min_x sum_{i=1}^{m} d_i^2
      = min_x sum_{i=1}^{m} lVert P_i-xrVert_2^2
      $$



      Consider the square of the 2-norm of the block matrix of size $mntimes 1$ (tall vector),
      $$
      begin{bmatrix}
      P_1-x \
      P_2-x \
      vdots \
      P_m-x
      end{bmatrix}
      $$



      The square of the 2-norm of this matrix is exactly $sum_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 $sum_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-Ax$,
      $$
      begin{bmatrix}
      P_1-x \
      P_2-x \
      vdots \
      P_m-x
      end{bmatrix}
      =
      begin{bmatrix}
      P_1\
      P_2 \
      vdots \
      P_m
      end{bmatrix}
      -
      begin{bmatrix}
      I \
      I \
      vdots \
      I
      end{bmatrix}
      x
      $$
      where $I$ is the $ntimes n$ identity.



      To find $x$ we then solve the least squares problem $min_x lVert b-Ax rVert_2$.






      share|cite|improve this answer









      $endgroup$
















        0












        0








        0





        $begingroup$

        Suppose the polygon has vertices $P_1,ldots, P_m inmathbb{R}^n$. The distance $d_i$ from a point $x$ to $P_i$ is simply $d_i = lVert{P_i-x}rVert_2$. We would like to minimize the sum of squares of distances. That is, find $x$ solving:
        $$
        min_x sum_{i=1}^{m} d_i^2
        = min_x sum_{i=1}^{m} lVert P_i-xrVert_2^2
        $$



        Consider the square of the 2-norm of the block matrix of size $mntimes 1$ (tall vector),
        $$
        begin{bmatrix}
        P_1-x \
        P_2-x \
        vdots \
        P_m-x
        end{bmatrix}
        $$



        The square of the 2-norm of this matrix is exactly $sum_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 $sum_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-Ax$,
        $$
        begin{bmatrix}
        P_1-x \
        P_2-x \
        vdots \
        P_m-x
        end{bmatrix}
        =
        begin{bmatrix}
        P_1\
        P_2 \
        vdots \
        P_m
        end{bmatrix}
        -
        begin{bmatrix}
        I \
        I \
        vdots \
        I
        end{bmatrix}
        x
        $$
        where $I$ is the $ntimes n$ identity.



        To find $x$ we then solve the least squares problem $min_x lVert b-Ax rVert_2$.






        share|cite|improve this answer









        $endgroup$



        Suppose the polygon has vertices $P_1,ldots, P_m inmathbb{R}^n$. The distance $d_i$ from a point $x$ to $P_i$ is simply $d_i = lVert{P_i-x}rVert_2$. We would like to minimize the sum of squares of distances. That is, find $x$ solving:
        $$
        min_x sum_{i=1}^{m} d_i^2
        = min_x sum_{i=1}^{m} lVert P_i-xrVert_2^2
        $$



        Consider the square of the 2-norm of the block matrix of size $mntimes 1$ (tall vector),
        $$
        begin{bmatrix}
        P_1-x \
        P_2-x \
        vdots \
        P_m-x
        end{bmatrix}
        $$



        The square of the 2-norm of this matrix is exactly $sum_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 $sum_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-Ax$,
        $$
        begin{bmatrix}
        P_1-x \
        P_2-x \
        vdots \
        P_m-x
        end{bmatrix}
        =
        begin{bmatrix}
        P_1\
        P_2 \
        vdots \
        P_m
        end{bmatrix}
        -
        begin{bmatrix}
        I \
        I \
        vdots \
        I
        end{bmatrix}
        x
        $$
        where $I$ is the $ntimes n$ identity.



        To find $x$ we then solve the least squares problem $min_x lVert b-Ax rVert_2$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 26 '18 at 19:01









        tchtch

        783310




        783310






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid …



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053149%2fleast-squares-circumcenter-of-polygons%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            -

            Popular posts from this blog

            Bressuire

            Image
            .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
            Read more

            Cabo Verde

            Image
              Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º) ...
            Read more

            Gyllenstierna

            Image
            .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
            Read more