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

Solution 278962

3 Comments

3 Comments

James on 11 Jul 2013

Strange, as this passes all of the tests on my box. (How did I pass a random test, and fail the hard coded ones?!?) Maybe a bsxfun issue?

Richard Zapor on 12 Jul 2013

Rounding errors of sqrt. Possible fix circle(3)+10*eps(circle(3)) and r+10*eps(r)

James on 15 Jul 2013

Better, but still not quite there. With those fixes, it passes everything but test 2. I'll try a couple more changes, and then just throw in a hard coded hack for case 2. (Or maybe I'll just ask Tim for his solution. :-)

Solution 272633

1 Comment

1 Comment

Richard Zapor on 10 Jul 2013

Another astounding solution by Tim using complex numbers and for loops that create vectors. Example of for loop vectorization: for i=nchoosek(3:6,2)',i,end. Very nice mthod.

Problem Recent Solvers5

Problem Tags

Community Treasure Hunt

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

Start Hunting!