Problem 42765. Maximize Non-Co-Planar Points in an N-Cube

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>This Challenge is to find a set with the maximum number of integer points that create planar surfaces with a maximum of three points from the set. No four points may be co-planar. Given the size N and the number of expected points Q find a set of Q points. Only N=2/Q=5 and N=3/Q=8 will be tested. N=4/Q=10 or N=5/Q=13 are too large to process.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[N=2 contains 8 points [0,0,0;0,1,0;1,0,0;1,1,0;0,0,1;0,1,1;1,0,1;1,1,1]\nN=3 contains 27 points [0,0,0;0,0,1;0,0,2;...2,2,2]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output is a Qx3 matrix of the non-co-planar points.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Reference: The</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://68.173.157.131/Contest/Tetrahedra\"><w:r><w:t>March 2016 Al Zimmermann Non-Coplanar contest</w:t></w:r></w:hyperlink><w:r><w:t> is N=primes less than 100. Maximize the number of points in an NxNxN cube with no 4 points in a common plane.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Theory: The N=2 and N=3 cases can be processed by brute force if care is taken. Assumption of [0,0,0] greatly reduces number of cases. Solving</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/42762-is-3d-point-set-co-planar\"><w:r><w:t>Cody Co-Planar Check</w:t></w:r></w:hyperlink><w:r><w:t> may improve speed.</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>"}]}

This Challenge is to find a set with the maximum number of integer points that create planar surfaces with a maximum of three points from the set. No four points may be co-planar.
Given the size N and the number of expected points Q find a set of Q points. Only N=2/Q=5 and N=3/Q=8 will be tested. N=4/Q=10 or N=5/Q=13 are too large to process.<pre class="language-matlab">N=2 contains 8 points [0,0,0;0,1,0;1,0,0;1,1,0;0,0,1;0,1,1;1,0,1;1,1,1]
N=3 contains 27 points [0,0,0;0,0,1;0,0,2;...2,2,2]
</pre>Output is a Qx3 matrix of the non-co-planar points.Reference: The <a href = "http://68.173.157.131/Contest/Tetrahedra">March 2016 Al Zimmermann Non-Coplanar contest</a> is N=primes less than 100. Maximize the number of points in an NxNxN cube with no 4 points in a common plane.Theory: The N=2 and N=3 cases can be processed by brute force if care is taken. Assumption of [0,0,0] greatly reduces number of cases. Solving <a href = "http://www.mathworks.com/matlabcentral/cody/problems/42762-is-3d-point-set-co-planar">Cody Co-Planar Check</a> may improve speed.

Solve

Solution Stats

7 Solutions
6 Solvers

Last Solution submitted on Apr 20, 2020

Last 200 Solutions

Problem Recent Solvers6

Problem Tags

brute force meshgrid nchoosek puzzle speed topology zimmermann

Community Treasure Hunt

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

Start Hunting!

Problem 42765. Maximize Non-Co-Planar Points in an N-Cube

Solution Stats

Last 200 Solutions

Problem Recent Solvers6

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 42765. Maximize Non-Co-Planar Points in an N-Cube

Solution Stats

Last 200 Solutions

Problem Recent Solvers6

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players