Problem 1651. Circumcircle Points

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Determine the radius of the minimum sized circle that encompasses all the points.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Per</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf\"><w:r><w:t>Smallest Sphere Paper</w:t></w:r></w:hyperlink><w:r><w:t> this question was first addressed by Sylvester in 1857, Megiddo in 1982, and optimized by Emo Welzl in 1991.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> Points (eg [0 0;0 1;2 0]) Minimum of 3 points</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> r (radius of optimally centered circle)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r><w:r><w:t> [0 0;0 1;2 0] yields [xc,yc,r] [1 .5 1.118] Output r=1.118</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Theory:</w:t></w:r><w:r><w:t> Best Circumcircle may occur in two ways:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>1) Center of Line connecting pair with maximum separation, or</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>2) A circle utilizing three points from the set</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Related Challenges:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1336-geometry-find-circle-given-3-non-colinear-points/solutions/map\"><w:r><w:t>Circle from 3 Points</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/554-is-the-point-in-a-circle/solutions/map\"><w:r><w:t>Are Points in Circle</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Warning:</w:t></w:r><w:r><w:t> Rounding Errors may cause solution errors. Usage of 10*eps(r) may be appropriate.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Determine the radius of the minimum sized circle that encompasses all the points.Per <a href = "http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf">Smallest Sphere Paper</a> this question was first addressed by Sylvester in 1857, Megiddo in 1982, and optimized by Emo Welzl in 1991.Input: Points (eg [0 0;0 1;2 0]) Minimum of 3 pointsOutput: r (radius of optimally centered circle)Example: [0 0;0 1;2 0] yields [xc,yc,r] [1 .5 1.118] Output r=1.118Theory:
Best Circumcircle may occur in two ways:1) Center of Line connecting pair with maximum separation, or2) A circle utilizing three points from the setRelated Challenges:<a href = "http://www.mathworks.com/matlabcentral/cody/problems/1336-geometry-find-circle-given-3-non-colinear-points/solutions/map">Circle from 3 Points</a><a href = "http://www.mathworks.com/matlabcentral/cody/problems/554-is-the-point-in-a-circle/solutions/map">Are Points in Circle</a>Warning: Rounding Errors may cause solution errors. Usage of 10*eps(r) may be appropriate.

Determine the radius of the minimum sized circle that encompasses all the points.

Per <http://www.inf.ethz.ch/personal/gaertner/texts/own_work/esa99_final.pdf Smallest Sphere Paper> this question was first addressed by Sylvester in 1857, Megiddo in 1982, and optimized by Emo Welzl in 1991.

*Input:* Points  (eg [0 0;0 1;2 0])  Minimum of 3 points

*Output:* r  (radius of optimally centered circle)

*Example:*  [0 0;0 1;2 0]  yields [xc,yc,r] [1 .5 1.118] Output r=1.118

*Theory:*
Best Circumcircle may occur in two ways:

1) Center of Line connecting pair with maximum separation, or

2) A circle utilizing three points from the set

*Related Challenges:*

<http://www.mathworks.com/matlabcentral/cody/problems/1336-geometry-find-circle-given-3-non-colinear-points/solutions/map Circle from 3 Points>

<http://www.mathworks.com/matlabcentral/cody/problems/554-is-the-point-in-a-circle/solutions/map Are Points in Circle>

*Warning:* Rounding Errors may cause solution errors. Usage of 10*eps(r) may be appropriate.

Solve

Solution Stats

64 Solutions
5 Solvers

Last Solution submitted on Dec 27, 2021

Last 200 Solutions

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers5

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1651. Circumcircle Points

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Problem 1651. Circumcircle Points

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers5

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Players