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.

Latham

I think it would be helpful to explain the output you need for oddly shaped polygons- a triangle or other regular polygon (by regular I mean all side lengths and angles equal), your solution's trivial, and a solution that satisfies a simple shape may be inadequate for a less regular one. – Pollinosis

I thought of an example of a polygon with which I'm not clear on the output you would want. I obviously can't draw it in comments, but the vertices have the coordinates (0,3), (1,6), (2,5), (2,1), (1,0). Would you potentially need a solution to support a shape like this, and if so, what output would you expect? – Pollinosis

Added an example covering your squashed-pentagon example. Thanks for the suggestion - I think it helps clarify the problem. – Latham

With those criteria, would the optimal output of my example not simply be a circle (radius 3, centred on [1,3])? Your original example however could not be done with a circle. I think any shape where a circle centred around the midpoint between the two most distant vertices will encompass all other vertices would have the circle as the optimal solution. In the case of the triangle or any other regular polygon with an odd number of sides, this wouldn't work. – Pollinosis

I think you are right - updating question to reflect this. You don't happen to know of a good package where I can a) draw the figures and b) query for their areas afterwards, ideally without accumulating precision losses, do you? – Latham

A circle's essentially just the natural conclusion of an algorithm that iteratively adds new vertices as required- it might be worth looking into the possibility of a circle based on the mid-point of the two most distant vertices as a STARTING point, and developing an algorithm that then adjusts the shape to incorporate any vertices that are outside the circle, starting with the most distant from the centre. Not really sure how to do that though, I'd need to give it more thought. – Pollinosis

Not too sure about "natural conclusion" - look at the triangle example above; it is the result of intersections, not incremental additions. – Latham

In that example, no, as no additions were required. In my example, it is necessary. I suppose I should have said the natural conclusion in some cases; I tried working through how you would derive a solution for a square (by hand), and after one iteration it ended up an octagon, then a 16-sided shape after a second iteration and continued until I ended up with a circle. – Pollinosis

It may be worth pointing out that both shapes in the pentagon example (the pink circle and the slightly smaller light blue shape) are maximal. Maximal means they can not be made incrementally larger while still meeting the requirements; it does not mean maximum. A circle, when a solution (see Flynn1179's second comment), is always the shape of maximum area; but both the circle and the blue shape are maximal, in that they can not be enlarged without exceeding the diameter. – California

I've been struggling to think of a good way to make this idea work, but I'm not having much luck- basically, I think a solution lies in an algorithm that STARTS with a circle, using the two most distant vertices as a diameter, and iteratively adjusts that shape to add in the vertex most distant from the centre of the shape. I'm not sure how to define that 'adjustment' part of the algorithm though. I'm trying to work with how your triangle would be calculated by such an algorithm, but I can't quite get my head round it. – Pollinosis

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.

Huonghupeh

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.

Pollinosis

There is a whole line of points equidistant from any two neighboring vertices. – Latham

But only two where that distance is equal to your diameter. – Pollinosis

(To close this answer - the question is not 'how do I calculate an additional point within the shape-border', but rather 'how do I efficiently find the whole diameter-constrained shape') – Latham

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.

Ingalls

Call the diameter of your polygon 'd'. If you intersect 4 radius-of-d circles, yes, the diameter of the result is too large. Then you progress as in the second example above, intersecting more radius-of-d circles centered on the newly created vertices. – Latham

@tucuxi: I understand your algorithm, but it still doesn't give the required maximal area result. – Ingalls