Smooth a convex polygonal shape so that it becomes as large as possible while retaining diameter

Question

Given a convex polygon, I am trying to grow its shape (as in "maximal area") while preserving its diameter. The diameter is defined as the length of the longest segment that can be placed within the polygon. Since the polygon is convex, I assume that this diameter can always be found by scanning all vertex pairs.

For example, given an equilateral triangle as an input polygon, the diameter of the triangle is the length of any edge; smoothing this would result in 3 circle segments as shown in the image

For arbitrary convex polygons, a very inefficient algorithm is to compute the intersection of the maximum-diameter radius circles centered on each polygon vertex; this is what I am currently using (in Java). Is there anything better? Any pseudo-code or pointer to algorithm will be appreciated.

Another example: a squashed pentagon and its corresponding diameter-preserving maximal shape. The idea is that you cannot increase the area of this shape without increasing the diameter (that is, making it possible to draw a straight line within the bounds of the shape which is longer than the original diameter). In this particular case, it seems that a single circle with radius = polygon_diameter/2 (pink) is better than the intersection of multiple larger circles with radius = polygon_diameter (light-blue). The second image superimposes both areas to make comparison easier, but areas should completely enclose the polygon.

Answer 1

Computing the intersection's simpler than it looks; all you actually need to do is determine the point that's equidistant from two neighbouring vertices; you'll end up with two points, but whichever is closest to the centre of the shape will almost certainly be the right one; It might even be guaranteed for convex polygons, but mathematical proofs aren't my strong point.

Answer 2

It seems to me that your current algorithm is not only inefficient but also incorrect. Take the rectangle (0,0)-(10,0)-(10,1)-(0,1) which currently has a diameter of a bit over 10. Intersect circles with that radius around all the corner, and you will end up with a pretty large lens-shaped thing with a diameter well in excess of 16. So that algorithm doesn't work.

You could fix the excess diameter by again intersecting the shape with a diameter-sized circle around one of the new vertices, but your choice of the vertex to use would be arbitrary. And no matter the choice, the resulting “bloated triangle” shape still appears smaller than the circumcircle of the rectangle. I assume that in my case, that circumcircle would be the optimal solution, but I can't see an easy way to modify your algorithm in such a way as to find that solution, while retaining its generality.

This is just a gut feeling, but I doubt that the desired output is uniquely defined by the input polygon and your requirements. Although I don't have an example to this effect yet, I believe that there might be input polygons for which several “smoothed” shapes exists, all with the same area and same diameter, but still not congruent to one another. Might be worth taking this to the math stack exchange for further discussion of this existential question.