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.

Solve

Solution Stats

54 Solutions
4 Solvers

Last Solution submitted on Dec 12, 2019

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 Solvers4

Problem Tags

circle circumcenters circumscribe delaunaytri eps geometry

Problem 1651. Circumcircle Points

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author236

Problem Tags

Problem 1651. Circumcircle Points

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author236

Problem Tags

Players