Glätten Sie eine konvexe polygonale Form, so dass sie so groß wie möglich wird, während der Durchmesser beibehalten wird

Es stellt sich heraus, dass diese Frage bereits auf Math Overflow gestellt wurde, und die Leute folgerten, dass es wahrscheinlich eine sein würde schwieriges Problem. Es gibt sogar einige unbeantwortete Grundfragen wie etwa ob eine solche Form einzigartig ist.

Ich habe also keine genaue Lösung, aber hoffentlich bringt dich das näher oder gibt dir zumindest ein paar Ideen.

Hintergrund

Der Einfachheit halber können wir ohne Verlust der Allgemeinheit annehmen, dass der Durchmesser des ursprünglichen Polygons 1 ist.

Zur Verallgemeinerung des Satzes von Blaschke-Lebesgue für Disk-Polygone (M. Bezdek, 2009) beschreibt eine Reihe nützlicher Konzepte. Relevante sind:

• Ein Disk-Polygon ist informell ein konvexer Satz, der ein "fettes" Polygon bildet, bei dem Kanten durch Krümmungsbögen 1 ersetzt werden.
• Die Menge der Punkte, die wir zu einer Menge von Punkten D hinzufügen können, so dass die resultierende Form höchstens den Durchmesser 1 hat, heißt Doppelscheibenpolygon D * von D .
• das Duale des dualen D ** heißt die konvexe Spindelhülle von D : es ist das kleinste Plattenpolygon, das D enthält .

Anstatt mit Polygonen zu arbeiten, reicht es aus, mit Disk-Polygonen zu arbeiten: Wir können das ursprüngliche Polygon immer durch seine konvexe Spindel ersetzen, ohne das Ergebnis zu verändern.

Wir haben das D ⊆ D * , wenn D den Durchmesser 1 hat und D = D * genau dann, wenn D konstante Breite 1 hat. Die Lösung S wird konstante Breite 1 haben (was natürlich nicht ausreicht). Deshalb D S wenn und nur wenn D S D : insbesondere, um S zu approximieren, müssen wir nur eine genügend große disk-polygonale Teilmenge D von S finden. Dies ist sehr mächtig, da, wie wir sehen werden, die Aussage, dass ein Punkt zu S gehört, nicht zu einer oberen Grenze und zu einer unteren Grenze auf führt S (und daher sein Bereich).

Theoretische Probleme

Um einen effizienten Algorithmus zu finden, sollten Sie folgende Fragen beantworten:

• ist eine global optimale Form, d. h. eine Lösung, die notwendigerweise einzigartig ist?
• ist eine lokal optimale Form unbedingt einzigartig?
• ist die isodiametrische Hülle eines Polygons notwendigerweise ein Kreis mit dem Durchmesser 1 oder ein Reuleaux-Polygon mit der Breite 1?
• Wenn ja, sind die Eckpunkte des Reuleaux-Polygons von endlich vielen Einheitsradius-Kreisschnittpunkten ausgehend von den Eckpunkten des ursprünglichen Polygons?
abgeleitet
• Gibt es eine Schranke für die Anzahl der Scheitelpunkte des Reuleaux-Polygons als Funktion der Anzahl der Scheitelpunkte des ursprünglichen Polygons?

Fragen zum Bereich der Disk-Polygone können schwierig sein: Das Problem wurde gelöst in Disketten auseinander schieben - die Kneser-Poulsen-Vermutung in der Ebene (K. Bezdek, R. Connelly, 2001) war eine einfache Frage bezüglich des Bereichs der Schnittpunkte von Scheiben in der Ebene, die für eine lange Zeit ungelöst geblieben war.

Praktische (?) Ansätze

Globale Suche :
Beginnen Sie mit der spindelkonvexen Hülle des Polygons und konstruieren Sie träge einen unendlichen Suchbaum mit zunehmenden Plattenpolygonen, wobei jeder Knoten die Menge aller Konstanten mit der Breite X , die D erfüllen, partitioniert ⊆ X ⊆ D * , abhängig davon, ob ein Punkt x von D * \ D gehört oder gehört nicht zu X . Der linke Zweig ist die Spindel konvexe Hülle von D ∪ { x }. Der rechte Zweig ist das Doppelplattenpolygon von D * ∩ { y : x ∉ [ y , < em> z ] für alle z in D }.

Wenn Sie x nicht sehr schlecht wählen (z. B. an der Grenze von D * \ D ), sollte jeder unendliche Pfad dieses Baums konvergieren zu einer Kurve mit konstanter Breite.

Die Idee ist, den Baum auf eine etwas breitere Art und Weise zu erkunden. Hoffentlich, wenn x auf eine sinnvolle Weise gewählt wird, werden Sie in der Lage sein, alle Zweige zu verwerfen, wo D * eine kleinere Fläche als die größte Fläche von hat D bisher gefunden, da solche Zweige die Lösung nicht enthalten können. Dann werden Sie eine Reihe von Disk-Polygonen haben, die zu der Menge von Lösungen für das Problem konvergieren, wenn Sie tiefer in den Baum gehen, hoffentlich nicht zu schnell wachsen.

Einige Heuristiken für x könnten lauten: nimm einen Punkt so nah wie möglich an das Innere von D * \ D , nimm ein zufälliges Ergebnis Punkt und so weiter. Es kann auch interessant sein, eine gewisse Menge an Tiefensuche einzubeziehen, um genauere untere Grenzen des Bereichs der Lösung zu erhalten, die es erlauben würden, ganze Zweige des Baumes früher zu verwerfen.

Lokale Suche :
Wir könnten auch nur mit Plattenpolygonen mit konstanter Breite (Reuleaux-Polygone) arbeiten und den Effekt kleiner Abweichungen betrachten. Aber der Suchraum ist ziemlich groß, so dass es nicht klar ist, wie das geht.

Berechnen der Kreuzung ist einfacher als es aussieht; Sie müssen nur den Punkt bestimmen, der von zwei benachbarten Ecken gleich weit entfernt ist. Sie werden mit zwei Punkten enden, aber dasjenige, das der Mitte der Form am nächsten kommt, wird mit ziemlicher Sicherheit das Richtige sein. Es könnte sogar für konvexe Polygone garantiert sein, aber mathematische Beweise sind nicht meine Stärke.

Es scheint mir, dass Ihr aktueller Algorithmus nicht nur ineffizient, sondern auch inkorrekt ist. Nimm das Rechteck (0,0)-(10,0)-(10,1)-(0,1) , das momentan einen Durchmesser von etwas über 10 hat. Durchschneide Kreise mit diesem Radius um die ganze Ecke und du wirst mit einem ziemlich großen linsenförmigen Ding mit einem Durchmesser von weit über 16 enden Dieser Algorithmus funktioniert nicht.

Sie könnten den überschüssigen Durchmesser korrigieren, indem Sie die Form erneut mit einem kreisförmigen Durchmesser um einen der neuen Scheitelpunkte schneiden, aber die Wahl des zu verwendenden Scheitelpunkts wäre willkürlich. Und unabhängig von der Wahl erscheint die resultierende "aufgeblähte Dreiecksform" immer noch kleiner als der Umkreis des Rechtecks. Ich nehme an, dass in meinem Fall dieser Umkreis die optimale Lösung wäre, aber ich sehe keinen einfachen Weg, Ihren Algorithmus so zu modifizieren, dass er diese Lösung findet, während er seine Allgemeinheit beibehält.

Das ist nur ein Bauchgefühl, aber ich bezweifle, dass die gewünschte Ausgabe durch das Eingabe-Polygon und Ihre Anforderungen eindeutig definiert ist. Obwohl ich noch kein Beispiel dafür habe, glaube ich, dass es Eingabepolygone geben könnte, für die mehrere "geglättete" Formen existieren, die alle die gleiche Fläche und den gleichen Durchmesser haben, aber immer noch nicht deckungsgleich sind. Vielleicht lohnt es sich, dies zum Mathe-Stapel-Austausch mitzunehmen, um diese existenzielle Frage weiter zu diskutieren.