Least Squares Circumcenter of Polygons












0














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.










share|cite|improve this question
























  • 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.
    – tch
    Dec 26 '18 at 18:17










  • @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.
    – pacosta
    Dec 26 '18 at 18:41












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












  • 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?
    – lulu
    Dec 26 '18 at 19:13












  • 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...
    – lulu
    Dec 26 '18 at 19:15
















0














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.










share|cite|improve this question
























  • 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.
    – tch
    Dec 26 '18 at 18:17










  • @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.
    – pacosta
    Dec 26 '18 at 18:41












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












  • 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?
    – lulu
    Dec 26 '18 at 19:13












  • 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...
    – lulu
    Dec 26 '18 at 19:15














0












0








0







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.










share|cite|improve this question















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















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 26 '18 at 21:10

























asked Dec 26 '18 at 17:52









pacosta

1485




1485












  • 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.
    – tch
    Dec 26 '18 at 18:17










  • @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.
    – pacosta
    Dec 26 '18 at 18:41












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












  • 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?
    – lulu
    Dec 26 '18 at 19:13












  • 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...
    – lulu
    Dec 26 '18 at 19:15


















  • 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.
    – tch
    Dec 26 '18 at 18:17










  • @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.
    – pacosta
    Dec 26 '18 at 18:41












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












  • 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?
    – lulu
    Dec 26 '18 at 19:13












  • 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...
    – lulu
    Dec 26 '18 at 19:15
















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.
– tch
Dec 26 '18 at 18:17




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.
– tch
Dec 26 '18 at 18:17












@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.
– pacosta
Dec 26 '18 at 18:41






@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.
– pacosta
Dec 26 '18 at 18:41














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






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














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?
– lulu
Dec 26 '18 at 19:13






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?
– lulu
Dec 26 '18 at 19:13














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...
– lulu
Dec 26 '18 at 19:15




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...
– lulu
Dec 26 '18 at 19:15










1 Answer
1






active

oldest

votes


















0














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





















    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














    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


























      0














      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
























        0












        0








        0






        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












        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









        tch

        34919




        34919






























            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.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • 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.


            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

            Human spaceflight

            Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

            張江高科駅