29
\$\begingroup\$

Inspired by this challenge, as well as a problem I've been working on

Problem:

Given a non-empty set of points in 3D space, find the diameter of the smallest sphere that encloses them all. The problem is trivial if the number of points is three or fewer so, for the sake of this challenge, the number of points shall be greater than three.

Input: A list of 4 or more points, such that no three points are colinear and no four points are coplanar. Coordinates must be floats, and it is possible that two or more points may share a coordinate, although no two points will be the same.

Output: The diameter of the set (the diameter of the smallest sphere that encloses all points in the set), as a float. As has been pointed out, this is not necessarily the same as the largest distance between any two points in the set.

Rules:

  1. You may assume that the points are not colinear.

  2. The smallest program (in bytes) wins. Please include the language used, and the length in bytes as a header in the first line of your answer.

Example I/O:

Input:

 [[4, 3, 6], [0, 2, 4], [3, 0, 4], [0, 9, 1]]

Output: 9.9498743710662

Input:

 [[8, 6, 9], [2, 4, 5], [5, 5, 4], [5, 1, 6]]

Output: 7.524876236605994

Improve this question
\$\endgroup\$
12
  • 4
    \$\begingroup\$ Suggest a test case where the diameter is not just the maximum distance between any two input points, such as [0,0,0],[1,0,0],[0,1,0],[0,0,1]. \$\endgroup\$
    – att
    Dec 29, 2020 at 1:51
  • 1
    \$\begingroup\$ Suggest adding a test case with floats with a decimal since you said they would be floats. \$\endgroup\$
    – EasyasPi
    Dec 29, 2020 at 2:48
  • 4
    \$\begingroup\$ I've cast the final close vote. Cody Gray's comment needs to be addressed in the body of the question. Otherwise more answers based on the distance between the two furthest points will be posted - and it's apparently not clear if this is allowed. It seems the only reason for this interpretation was a mistake in the second test case, which has now been corrected, but it would seem it needs to be called out explicitly to stop these answers \$\endgroup\$
    – Level River St
    Dec 30, 2020 at 4:07
  • 3
    \$\begingroup\$ @KeithMadison Can you add a test case containing five or more points? And it'd be great to have some test cases to demonstrate that the sphere can be defined by 4, 3, or 2 of the input points. \$\endgroup\$
    – Bubbler
    Dec 30, 2020 at 7:17
  • 3
    \$\begingroup\$ Given that several of the answers here (and one I was planning to post...) have been rendered invalid by the clarification to the rules, perhaps a new question should be started that focuses simply on determining the maximum Euclidean distance between a set of 3D points? \$\endgroup\$
    – Cody Gray
    Dec 30, 2020 at 10:03

2 Answers 2

Reset to default
19
\$\begingroup\$

Wolfram Language (Mathematica), 33 bytes

2#2&@@#~BoundingRegion~"MinBall"&

Try it online!

Nearly exactly the same as the Mathematica answer to the 2D version. Works for input points of any dimension.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Python 3, 80 bytes

lambda l:2*m.get_bounding_ball(numpy.array(l))[1]**.5
import numpy,miniball as m

Try it online! (can't get it to work on TIO - no PyPI miniball module and won't let me install it through code - but works fine on my laptop)

Uses PyPI's miniball module and works in any dimension.

Inputs a list of floating-point points (at least one coordinate of one point must be a float - i.e. have a decimal point - or numpy gets upset) and returns the diameter of the smallest enclosing circumsphere.

How?

PyPI's module miniball's function get_bounding_ball takes a numpy ndarray as the input points (with optional parameter epsilon which defaults to 1e-07) and returns the centre and the squared radius of the circumsphere as a tuple. We return double the square-root of the second element which is the diameter of the circumsphere.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.