Konvexe Polygonformulierung

7

Wir haben eine sortierte Liste von Seitenlängen, die zur Bildung eines Polygons verwendet werden können. Es gibt solche Werte ( ).nn1000

Jetzt müssen wir herausfinden, ob wir 10 dieser Werte verwenden können, um ein nicht entartetes konvexes Polygon zu bilden.

Wie gehen wir das an? Alles bis zur Größenordnung von ist akzeptabel. Besser wenn möglich. Ich brauche die allgemeine Vorstellung davon, wie es weitergehen soll, welche Eigenschaften konvexe Polygone hier ausgenutzt werden können usw.O(n2logn)

Alice
quelle
Darf ich fragen, wofür Sie das brauchen? Ihre spezifischen Grenzen für Eingabe und Zeit sind interessant ... So oder so, klingt nach einer schwierigen Frage.
Jmite
1
Zwei Beobachtungen: Konvexität ist nicht wichtig. Siehe dies: cs.mcgill.ca/~cs507/projects/1998/mas/main2.html Es ist leicht zu bestimmen, ob ein Polygon aus einer Reihe von Längen erstellt werden kann: mathoverflow.net/questions/96617/…
Chao Xu
Ist dies für das TKCONVEX-Problem bei Codechef ? Bei diesen Wettbewerben geht es darum, die relevanten Algorithmen oder zumindest die relevante Literatur selbst zu finden. (Beachten Sie, dass wir in der Informatik im Gegensatz zur Mathematik keine Richtlinien gegen laufende Wettbewerbe haben .)
Gilles 'SO - hör auf böse zu sein'
@ Gilles sogar der Algorithmus unten gibt eine WA. Dies reicht nicht aus, um das Problem zu beheben. Und wir sind Studenten, die nicht so gut programmieren können, aber wir wollen lernen. Und Wettbewerbe motivieren alle. Und wenn wir pro Wettbewerb sogar 10 neue Algorithmen lernen, ist der Gewinn enorm. Wenn uns jemand in die richtige Richtung weist (beachten Sie, dass nur Zeigen, keine Codes, nichts), besteht eine größere Wahrscheinlichkeit, dass wir den tatsächlichen Algorithmus für das Problem lernen. Ich versuche nur zu lernen. Wenn ich ein Problem mehr löse, wirkt sich das nicht auf die Rangliste aus. Also ich denke es ist egal, ob es uns beim Lernen hilft
Alice
Ich denke, Codechef hat ein Diskussionsforum, in dem Leute nach dem Ende des Wettbewerbs Lösungen veröffentlichen.
Chao Xu

Antworten:

6

Satz 1. Für jedes Polygon mit Kantenlängenfolgea1,,amgibt es ein konvexes Polygon mit der gleichen Kantenlängenfolge.

Beweis. Hier .

Definition. a1,,an Sein nnicht negative Reals. Es erfüllt (streng)n-gon Ungleichung wenn2einj<ich=1neinich für alle j.

Satz 2. Die Folgeein1,,einn ist eine Folge der Kantenlänge für ein Polygon, wenn es erfüllt ist n-gon Ungleichung.

Beweis. Hier . (Beachten Sie, dass der Beweis hier fortgeschrittene Mathematik erfordert und auch Satz 1 beweist.)

Das Problem reduziert sich auf:

Gegeben eine Folge von n nicht negative Reals, finde a k Elementteilfolge, die erfüllt k-gon Ungleichung.

Ein einfacher Algorithmus: Überprüfen Sie, ob einich,,einich+k- -1 ist eine Lösung für jeden 1ichn- -k+1. Wenn keiner von ihnen funktioniert, gibt es keine Lösung.

Beweis. Wenn wir eine Lösung habeneinich1,,einichk, finde den größten j, so dass einichj+1- -einichj>1, (dh es gibt eine Lücke). Wenn es keine solche Lücke gibt, sind wir fertig. Wenn es einen gibt, danneinich2,,einichj,einichj+1- -1,einichj+1,,einichkist auch eine Lösung. (Intuitiv haben wir das größte Element in der Lücke verwendet und das kleinste Element entfernt). Wir können diesen Schritt (höchstens) wiederholenk- -1Zeiten) und füllen Sie alle Lücken. Schließlich haben wir eine Lösung der Form erstellteinichk- -k+1,einichk- -k,,einichk- -1,einichk für einige ich.

Der Algorithmus kann naiv in ausgeführt werden Ö(kn)Zeit. Vielleicht gibt es einen intelligenteren Weg, dies zu tun.

Eine interessante Folgefrage:

Gegeben eine Folge von n Nicht negative Reals finden die längste Teilsequenz S., so dass jeder k Elementsequenz von S. befriedigt k-gon Ungleichung .

Chao Xu
quelle
Ist dieser Satz 2 eine Erweiterung der Dreiecksungleichung? Und warum ist Sortieren notwendig? Wir können jede k-Teilmenge der gegebenen Punkte wählen, die den zweiten Satz erfüllt.
Alice
Sie müssen nicht sortieren, das Sortieren verringert nur die zeitliche Komplexität: Nur prüfen Ö(n) Teilsequenzen statt 2n.
Chao Xu
scheint nicht zu funktionieren. Sind Sie sicher, dass wir nur nk-Polygone überprüfen müssen?
Alice
Bitte geben Sie ein Beispiel an, wenn dies nicht funktioniert.
Chao Xu
3
Es gibt einen etwas besseren Weg, dies zu tun. Halten Sie eine laufende Summe der letztenk Kanten (durch Hinzufügen einich+k zu und subtrahieren die einich von dieser laufenden Summe), und verwenden Sie diese laufende Summe, um die zu überprüfen k-gon Ungleichung. Dies reduziert die Zeit vonÖ(kn) zu Ö(n).
Peter Shor