Boundary region problem: smallest region that contains a set of sub-regions?

Is it possible to obtain the smallest region of a certain type that 
contains a set of sub-regions?  If so, how is it done?


Thanks in advance,
Rui Maciel

Too abstract for me to say anything. Can you make the problem more 
concrete?

-- 
 http://www.**--****.com/ 

Sure.  Let's consider all regions to be spheres and let's interpret "sub-
regions" as "spheres which are contained in a larger sphere".  To put the 
issue a bit more precisely, let's assume we are talking about a scene 
graph where multiple objects, each one contained in a bounding sphere, are 
organized in a bounding volume hiearchy.  Is it possible to calculate the 
smallest sphere which contains all objects?

On a side note, I mentioned "region" in the previous post as I wasn't 
bound to a specific geometry to use as a bounding volume.  Nonetheless, 
spheres appear to be nice at that.


Thanks in advance,
Rui Maciel

I haven't considered the problem of bounding spheres with a minimum-
volume sphere before. However, it must be at least as hard as minimum 
volume sphere for points. The latter has an algorithm with O(n) expected 
runtime, and can be found from:

"Smallest enclosing disks (balls and ellipsoids)"
 http://www.**--****.com/ 

However, the question is whether it can be generalized to bound spheres. 
Anyway, you shouldn't expect something too trivial. Things can be easier 
if you settle for an approximation (such as choosing the midpoint of 
center points and then looking at the farthest point for radius).

See also:

 http://www.**--****.com/ 

Axis-aligned boxes would be trivial to compute.

-- 
 http://www.**--****.com/ 

Unfortunately I can't access that article.  It appears it's behind a 
paywall of sorts.

 

I've hacked a brute force method to get the smallest bounding sphere.  It 
is a bit crude and I believe it will work poorly when compared with other 
alternatives. The method goes as follows:

Consider N sub-spheres and a bounding sphere.
1) setup a starting bounding sphere, which may be equal to the 1st sphere 
in the list. 
2) set the sub-sphere to be compared to the next sub-sphere in the list
3) check if the current test sub-sphere is contained in the current 
bounding sphere
   3.1) if it is then go to 4
   3.2) if it isn't then move the bounding sphere's center and resize it's 
radius in order to contain all the sub-spheres tested up to now, including 
the current test sub-sphere. go to 4
4)  if there are more sub-spheres in the list then move on to the next 
sub-sphere, restart at step 3).  If not then it's finished.


The following tests are applied:
- Check if sub-sphere is completely inside the bounding sphere
	Let C_0 be the coordinates for the bounding sphere's center, 
Ct for the test sub-sphere's center
	Let r_0, rt be the radiuses of the boundary sphere and sub-
sphere
	
if ( norm(Ct-C_0)  > r_0+rt) then the test sphere shares at least a point 
with the boundary sphere.  Therefore it is inside the sphere.

The new radius for the boundary sphere is:
r_1 = (r_0 + rt + norm(Ct-C_0) )/2

The new center for the boundary sphere is:
C_1 = (Ct-C0)*t +  C_0

with t = ( norm(Ct-C_0) + rt - r_0)/(2*norm(Ct-C_0))
 


Do you happen to know any good sources on that topic?


Thanks for the help,
Rui Maciel

I don't think this gives the minimum-volume sphere, for otherwise it 
would give a simple O(n) worst-case time algorithm for any dimension. 
But if the result is satisfactory, then maybe you are done:)


On each axis, pick the minimum of the minimum of the boxes, and the 
maximum of the maximum of boxes.

-- 
 http://www.**--****.com/