Monday, April 07, 2014

[xvxfupmr] Many bubbles

Given a set of areas, draw a diagram of regions with those areas minimizing the total perimeter.  This appears to be a problem for which no known algorithm is guaranteed to solve.  In three dimensions with only two regions, the solution is the standard double bubble.

Assuming a solution, form a graph of adjacent regions. (This graph could be complicated with toroidal regions.)  Given just this graph, how difficult is it to reconstruct the shape and borders of each region? I suspect this becomes an easier local minimization problem.

No comments :