Mixing
Worst-Case Addition to Smallest Enclosing Circle
$begingroup$
Imagine you have a convex polygon $p_1$ and put a smallest enclosing circle $SEC_1$ around it, the lengths of each side of the polygon $l_i$ can be anything and don't have to equal each other. Now, imagine on each side of the polygon, you place a (45-45-90) triangle where the $l_i$ is the base of each triangle and $l_i$ is across from (opposite) the 90 degree angle. The triangles and $p_1$ combine to form $p_2$, which is then surrounded by a smallest enclosing circle $SEC_2$. The question is: what is the shape of $p_1$ that would cause the largest increase (in diameter or area) of $SEC_1$ to $SEC_2$?
geometry analysis trigonometry upper-lower-bounds
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
$endgroup$
add a comment |
$begingroup$
Imagine you have a convex polygon $p_1$ and put a smallest enclosing circle $SEC_1$ around it, the lengths of each side of the polygon $l_i$ can be anything and don't have to equal each other. Now, imagine on each side of the polygon, you place a (45-45-90) triangle where the $l_i$ is the base of each triangle and $l_i$ is across from (opposite) the 90 degree angle. The triangles and $p_1$ combine to form $p_2$, which is then surrounded by a smallest enclosing circle $SEC_2$. The question is: what is the shape of $p_1$ that would cause the largest increase (in diameter or area) of $SEC_1$ to $SEC_2$?
geometry analysis trigonometry upper-lower-bounds
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
$endgroup$
add a comment |
$begingroup$
Imagine you have a convex polygon $p_1$ and put a smallest enclosing circle $SEC_1$ around it, the lengths of each side of the polygon $l_i$ can be anything and don't have to equal each other. Now, imagine on each side of the polygon, you place a (45-45-90) triangle where the $l_i$ is the base of each triangle and $l_i$ is across from (opposite) the 90 degree angle. The triangles and $p_1$ combine to form $p_2$, which is then surrounded by a smallest enclosing circle $SEC_2$. The question is: what is the shape of $p_1$ that would cause the largest increase (in diameter or area) of $SEC_1$ to $SEC_2$?
geometry analysis trigonometry upper-lower-bounds
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
$endgroup$
Imagine you have a convex polygon $p_1$ and put a smallest enclosing circle $SEC_1$ around it, the lengths of each side of the polygon $l_i$ can be anything and don't have to equal each other. Now, imagine on each side of the polygon, you place a (45-45-90) triangle where the $l_i$ is the base of each triangle and $l_i$ is across from (opposite) the 90 degree angle. The triangles and $p_1$ combine to form $p_2$, which is then surrounded by a smallest enclosing circle $SEC_2$. The question is: what is the shape of $p_1$ that would cause the largest increase (in diameter or area) of $SEC_1$ to $SEC_2$?
geometry analysis trigonometry upper-lower-bounds
geometry analysis trigonometry upper-lower-bounds
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
edited Jan 18 at 21:49
RoryHector
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
asked Jan 18 at 18:20
RoryHectorRoryHector
7914
7914
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I don't have a proof that it is optimal, but I suspect it is a square. At least this will give people a target to try to beat. The radius increases by a factor $sqrt 2$ so the area doubles.
Let us scale things so the radius of the original circle is $1$ and concentrate on one side of the polygon. We want both ends of the side to be on the circle or we could push one out to the circle without increasing $SEC_1$.
$DE$ is the side of the original polygon, so $g=h=1$. $DEF$ is the constructed triangle and $AF$ is the radius of $SEC_2$. Let $x=frac 12|DE|$. We note that $|AF|=x+sqrt{1-x^2}$. This is maximized when $x=frac 12sqrt 2, |AF|=sqrt 2$, which corresponds to one side of a square. I have assumed that the centers of $SEC_1$ and $SEC_2$ are the same, but otherwise I believe this is correct.
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
$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%2f3078591%2fworst-case-addition-to-smallest-enclosing-circle%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$
I don't have a proof that it is optimal, but I suspect it is a square. At least this will give people a target to try to beat. The radius increases by a factor $sqrt 2$ so the area doubles.
Let us scale things so the radius of the original circle is $1$ and concentrate on one side of the polygon. We want both ends of the side to be on the circle or we could push one out to the circle without increasing $SEC_1$.
$DE$ is the side of the original polygon, so $g=h=1$. $DEF$ is the constructed triangle and $AF$ is the radius of $SEC_2$. Let $x=frac 12|DE|$. We note that $|AF|=x+sqrt{1-x^2}$. This is maximized when $x=frac 12sqrt 2, |AF|=sqrt 2$, which corresponds to one side of a square. I have assumed that the centers of $SEC_1$ and $SEC_2$ are the same, but otherwise I believe this is correct.
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
$begingroup$
I don't have a proof that it is optimal, but I suspect it is a square. At least this will give people a target to try to beat. The radius increases by a factor $sqrt 2$ so the area doubles.
Let us scale things so the radius of the original circle is $1$ and concentrate on one side of the polygon. We want both ends of the side to be on the circle or we could push one out to the circle without increasing $SEC_1$.
$DE$ is the side of the original polygon, so $g=h=1$. $DEF$ is the constructed triangle and $AF$ is the radius of $SEC_2$. Let $x=frac 12|DE|$. We note that $|AF|=x+sqrt{1-x^2}$. This is maximized when $x=frac 12sqrt 2, |AF|=sqrt 2$, which corresponds to one side of a square. I have assumed that the centers of $SEC_1$ and $SEC_2$ are the same, but otherwise I believe this is correct.
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
$endgroup$
add a comment |
$begingroup$
I don't have a proof that it is optimal, but I suspect it is a square. At least this will give people a target to try to beat. The radius increases by a factor $sqrt 2$ so the area doubles.
Let us scale things so the radius of the original circle is $1$ and concentrate on one side of the polygon. We want both ends of the side to be on the circle or we could push one out to the circle without increasing $SEC_1$.
$DE$ is the side of the original polygon, so $g=h=1$. $DEF$ is the constructed triangle and $AF$ is the radius of $SEC_2$. Let $x=frac 12|DE|$. We note that $|AF|=x+sqrt{1-x^2}$. This is maximized when $x=frac 12sqrt 2, |AF|=sqrt 2$, which corresponds to one side of a square. I have assumed that the centers of $SEC_1$ and $SEC_2$ are the same, but otherwise I believe this is correct.
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
$endgroup$
I don't have a proof that it is optimal, but I suspect it is a square. At least this will give people a target to try to beat. The radius increases by a factor $sqrt 2$ so the area doubles.
Let us scale things so the radius of the original circle is $1$ and concentrate on one side of the polygon. We want both ends of the side to be on the circle or we could push one out to the circle without increasing $SEC_1$.
$DE$ is the side of the original polygon, so $g=h=1$. $DEF$ is the constructed triangle and $AF$ is the radius of $SEC_2$. Let $x=frac 12|DE|$. We note that $|AF|=x+sqrt{1-x^2}$. This is maximized when $x=frac 12sqrt 2, |AF|=sqrt 2$, which corresponds to one side of a square. I have assumed that the centers of $SEC_1$ and $SEC_2$ are the same, but otherwise I believe this is correct.
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
answered Jan 18 at 22:08
Ross MillikanRoss Millikan
298k23198371
298k23198371
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%2f3078591%2fworst-case-addition-to-smallest-enclosing-circle%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
