Least Squares Circumcenter of Polygons
$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
asked Dec 26 '18 at 17:52
pacostapacosta
1535
$endgroup$
|
show 2 more comments
$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
asked Dec 26 '18 at 17:52
pacostapacosta
1535
$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
|
show 2 more comments
$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
asked Dec 26 '18 at 17:52
pacostapacosta
1535
$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
asked Dec 26 '18 at 17:52
pacostapacosta
1535
asked Dec 26 '18 at 17:52
pacostapacosta
1535
edited Dec 26 '18 at 21:10
pacosta
asked Dec 26 '18 at 17:52
pacostapacosta
1535
asked Dec 26 '18 at 17:52
pacostapacosta
1535
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
|
show 2 more comments
$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
|
show 2 more comments
1 Answer
1
active
oldest
votes
$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$.
answered Dec 26 '18 at 19:01
tchtch
803310
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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$.
answered Dec 26 '18 at 19:01
tchtch
803310
$endgroup$
add a comment |
$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$.
answered Dec 26 '18 at 19:01
tchtch
803310
$endgroup$
add a comment |
$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$.
answered Dec 26 '18 at 19:01
tchtch
803310
$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$.
answered Dec 26 '18 at 19:01
tchtch
803310
answered Dec 26 '18 at 19:01
tchtch
803310
answered Dec 26 '18 at 19:01
tchtch
803310
answered Dec 26 '18 at 19:01
tchtch
803310
803310
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$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