arithma Given a set of circles of different radiuses, determine the minimum area polygon that contains all the circles. No two circles are intersecting (distance at least equal to sum of their radii). struct Circle { double x, y, radius; };
geek it should be the minimum area convex simple polygon otherwise one would approximate the circles by regular polygons and join those polygons with line segment (zero area).
arithma I forgot to include a constraint that I was thinking implicitly of. Each polygon's segment must be tanget to at least two circles. We're out of the puddle right? (I think this allows us to make a better fit than just convex). Let's add the simple constraint just in case :)
mesa177 Ok, so here's what I was thinking, the set of circles specified by different radii will be arranged in a triangle which inscribes the 3 circles with largest radii (this is the smallest polygon that could be formed to inscribe all the circles in the set and each segment of the triangle, ie smallest polygon, is tangent to at least two circles in the set). Of course, each segment of the triangle must be tangent to 2 out of the 3 largest circles where none of the circles is missed: in other words: if the segments on the triangle are S1, S2 and S3, then S1 must be tangent to C1 and C2, S2 must be tangent to C2 and C3, and S3 must be tangent to C1 and C3. Of course, the 3 largest circles will have to be arranged in such a manner that they form an inscribed triangle, so each circle will have to be tangent to at least one of the other circles, and one of these circles will have to be tangent to both of the remaining circles. Yet I have a question, if each 2 circles in the set constitute their own sets (let's dub them the name Vn of major set V, where each set Vn in V is a pair of circles and these sets Vn are either mutually exclusive or have only one circle in common), must each segment in the polygon correspond to only one set Vn (i.e each segment must be only tangent to the circles in one of the the sets Vn and no two segments correspond to the same set Vn)? If so, then the circles must be arranged in such a manner that they are tangent to each other in order to form the polygon with minimum area (I don't see another way for each of the polygon's segments being tangent to at least two circles of the set, the circles being inscribed in the polygon itself, and the area of the inscribing polygon is minimum). And here's another question: if each radius is designated by a set Rn in major set R, are the sets Rn mutually exclusive? In other words, are no 2 radii the same? If so, then the number of vertices of the polygon would be equal to the number of circles inscribed. If not, then there's a possibility for at least two circles to have the same radii, and the number of vertices on the polygon is less than that. I think some more constraints are needed :s
arithma Sorry mesa, got caught up in the contest. I'll read up and update you if anything is needed. But from skimming two days ago, I think we're still not aligned. Graphics coming up.