1

I have seen discussion on here about enclosing points in an ellipse, but is there an algorithm to enclose a set of of ellipses one one ellipse? Could the foci be used to approximate the ellipse that closes the set?

micc0
  • 325
  • 3
  • 11
  • I doubt that such an algorithm exists in general. There are a lots of attempts to solve "circle packing" problems (2D) and "sphere packing" (3D) which is hard enough and often serves as test for optimization tools. Some authors use "covering" rather than "packing". If all ellipses are oriented in parallel, they could be transformed into circles and vice versa. Do you just want to enclose the set as it is? Or do you want a dense packing? – Axel Kemper Jan 23 '13 at 23:37
  • I've found a related paper on enclosing ellipsoids in an ellipsoid: http://compgeom.com/~piyush/papers/emve.pdf Other papers deal with enclosing sets of points in an ellipse: http://www.inf.ethz.ch/personal/gaertner/texts/own_work/smell2exact_tr-b-97-03.pdf – Axel Kemper Jan 23 '13 at 23:59
  • The SO discussion on "bounding ellipses" was here: http://stackoverflow.com/questions/1768197/bounding-ellipse – Axel Kemper Jan 24 '13 at 00:09

1 Answers1

0

Here's a hint: what is the smallest set of points that you could compute from each of the ellipses so that a single ellipse containing those points would also contain every point on the given ellipses?

chepner
  • 497,756
  • 71
  • 530
  • 681
  • It's the entire boundary of the ellipse. Not clear to me how that helps? – tmyklebu Jan 23 '13 at 22:15
  • How many points on the surface of an ellipse would you need to compute its bounding box? – chepner Jan 24 '13 at 00:16
  • Four. You still need *all* of them to get the minimum bounding ellipse of a union of ellipses, though. – tmyklebu Jan 24 '13 at 05:52
  • If I give you those four points for two ellipses, and you create a third ellipse that contains those 8 points, what part of the two original ellipses falls outside the third ellipse? – chepner Jan 24 '13 at 14:14
  • 1
    Some part of the boundary could lie outside the third ellipse. How 'bout we think about circles instead. Take four little circles and put them at the vertices of a square. The smallest enclosing circle of the top, left, right, and bottom points of all four circles (16 points in total) will cut off the corners of those four little circles. – tmyklebu Jan 25 '13 at 16:22