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

It turns out this question was already asked on Math Overflow, and people concluded it was likely to be a difficult problem. There are even some unanswered basic questions such as whether such a shape is unique.

So I don't have an exact solution, but hopefully this will get you closer or at least give you some ideas.

Background

For simplicity we can assume without loss of generality that the diameter of the initial polygon is 1.

On a generalization of the Blaschke-Lebesgue theorem for disk-polygons (M. Bezdek, 2009) describes a number of useful concepts. Relevant ones include:

• a disk-polygon is, informally, a convex set that forms a "fat" polygon where edges are replaced with arcs of curvature 1.
• the set of points which we can add to a set of points D so that the resulting shape is of diameter at most 1 is called the dual disk-polygon D* of D.
• the dual of the dual D** is called the spindle convex hull of D: it is the smallest disk-polygon containing D.

Instead of working with polygons, it suffices to work with disk-polygons: we can always replace the original polygon with its spindle convex hull without changing the result.

We have that D ⊆ D* when D has diameter 1, and D = D* if and only if D has constant width 1. The solution S will have constant width 1 (although this is of course not sufficient). Therefore D ⊆ S if and only if D ⊆ S ⊆ D*: in particular, to approximate S, we only need to find a large enough disk-polygonal subset D of S. This is very powerful, because as we will see, saying that some point belongs or does not belong to S translates to both an upper bound and a lower bound on S (and therefore its area).

Theoretical problems

Ideally to find an efficient algorithm it would be useful to answer the following questions:

• is a globally optimal shape, i.e. a solution, necessarily unique?
• is a locally optimal shape necessarily unique?
• is the isodiametric hull of a polygon necessarily a circle of diameter 1 or a Reuleaux polygon of width 1?
• if so, are the vertices of the Reuleaux polygon derived from finitely many unit-radius circle intersections, starting from the vertices of the original polygon?
• is there a bound on the number of vertices of the Reuleaux polygon as a function of the number of vertices of the original polygon?

Questions on the area of disk-polygons can be difficult: the problem solved in Pushing disks apart - the Kneser-Poulsen conjecture in the plane (K. Bezdek, R. Connelly, 2001) was a simple question regarding the area of intersections of disks in the plane which had remained unsolved for a long time.

Practical(?) approaches

Global search:
Start with the spindle convex hull of the polygon, and lazily construct an infinite search tree of increasing disk-polygons where each node partitions the set of all constant-width X satisfying D ⊆ X ⊆ D*, depending on whether some point x of D* \ D belongs or does not belong to X. The left branch is the spindle convex hull of D ∪ {x}. The right branch is the dual disk-polygon of D* ∩ {y : x ∉ [y, z] for all z in D}.

Unless you choose x very poorly (e.g. on the boundary of D* \ D), every infinite path of that tree should converge to a constant-width curve.

The idea is to explore the tree in a somewhat breadth-first way. Hopefully, if x is chosen in a sensible way, you will be able to discard all the branches where D* has a smaller area than the greatest area of a D found so far, as such branches cannot contain the solution. Then you will have a set of disk-polygons that converge to the set of solutions to the problem as you go deeper in the tree, hopefully while not growing too fast.

Some heuristics for x could be: take a point as close as possible to the inside of D* \ D, take a random point, and so on. It may also be interesting to incorporate some amount of depth-first search to have more precise lower bounds of the area of the solution which would allow to discard whole branches of the tree sooner.

Local search:
We could also work only with constant-width disk-polygons (Reuleaux polygons), and look at the effect of small deviations. But the search space is pretty large, so it's not clear how to do that.

Answer 2

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 3

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.