Graphen mit Gleichgewichtsstressen
Final Report Abstract
Durch die Verbesserung der oberen Schranke für die Anzahl der Spannbäume die ein planarer Graph enthalten kann, wurde gezeigt, dass sich jedes 3D Polytop als ein kombinatorisch äquivalentes Polytop auf einem Gitter der Größe O(147.7n ) darstellen lässt. Die verbesserte obere Schranke für die Anzahl der Spannbäume beträgt 5.28n , wobei n die Anzahl der Knoten im Graphen ist. Diese Schranke wurde mit einer neuen probabilistischen Methode berechnet, welche die Anzahl der Spannbäume als ein Optimierungsproblem modelliert. Dieses Problems lässt sich auf ein lineares Programm mit unendlich vielen Variablen reduzieren. Gelöst wurde das lineare Programm durch analytische Verfahren, sowie Computer-unterstütztem Testen endlich vieler Szenarien. Bislang waren keine interessanten Klassen von Polytopen bekannt, die sich auf einem Gitter polynomieller Größe einbetten lassen. Es wurde ein Algorithmus entwickelt, der sogenannte Stapelpolytope (3D Polytope deren Graph ein planarer 3-Baum ist) auf ein solches Gitter einbettet. Die Konstruktion benutzt den üblichen Ansatz über Gleichgewichtsstresse, jedoch werden die gewünschten Stresse als Linearkombination von atomaren Gleichgewichtsstressen so aufgebaut, dass es durch Runden (nicht durch Skalieren) möglich ist, kleine ganzzahlige Koordinaten zu erhalten. Zum Finden der geeigneten Koeffizienten dieser Linearkombination wurde auf eine Technik aus der Datenstruktur Analyse zurückgegriffen. Eine wichtige Kenngröße für eine gute Zeichnung eines 3D Polytopes ist die Knotenauflösung, also der relative Mindestabstand zweier Knoten. Es wurde gezeigt, dass man durch die Modifikation eines Gleichgewichtsstresses eine ebene Zeichnung des 3D Polytopes konstruieren kann, welche ganzahlige und unterschiedliche x-Koordinaten benutzt. Daraus folgt, dass jedes 3D Polytop so gezeichnet werden kann, dass (1) seine Knoten paarweise mindestens Abstand 1 haben, und (2) es in einer Box mit Kantenlänge 2(n − 2) × 2 × 1 enthalten ist. Eine andere Konsequenz aus diesen Überlegungen ergibt, dass man jedes 3D Polytop auf einem O(n) × O(n) × 2O(n2 log n) Gitter realisieren kann. Beim Studium des Zusammenhangs zwischen dem Entfalten von Gelenksystemen und Gleichgewichtsstressen wurde eine neue Charakterisierung von sogenannten gespitzten Pseudo-triangulierungen gefunden. Konkret wurde gezeigt, dass man eine gespitzte Pseudo-triangulierung als eindeutiges Gelenksystem beschreiben kann, welches eine Gleichgewichtslast mit einem positiven Stress im Inneren auflöst. In diesem Zusammenhang ergibt sich ein alternativer Beweis für die Korrektheit des PPT-Polytopes.
Publications
-
Drawing 3-polytopes with good vertex resolution. In David Eppstein and Emden R. Gansner, editors, Graph Drawing, volume 5849 of Lecture Notes in Computer Science, pages 33–44. Springer, 2009
André Schulz
-
Resolving loads with positive interior stresses. In Frank K. H. A. Dehne, Marina L. Gavrilova, Jörg-Rüdiger Sack, and Csaba D. Tóth, editors, WADS, volume 5664 of Lecture Notes in Computer Science, pages 530–541. Springer, 2009
Günter Rote and André Schulz
-
Bounded-degree polyhedronization of point sets. In CCCG, pages 99–102, 2010
Gill Barequet, Nadia Benbernou, David Charlton, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Anna Lubiw, André Schulz, Diane L. Souvaine, Godfried T. Toussaint, and Andrew Winslow
-
Fréchet distance of surfaces: Some simple hard cases. In Mark de Berg and Ulrich Meyer, editors, ESA (2), volume 6347 of Lecture Notes in Computer Science, pages 63–74. Springer, 2010
Kevin Buchin, Maike Buchin, and André Schulz
-
On the number of spanning trees a planar graph can have. In Mark de Berg and Ulrich Meyer, editors, ESA (1), volume 6346 of Lecture Notes in Computer Science, pages 110–121. Springer, 2010
Kevin Buchin and André Schulz
