Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs

Streinu, Ileana (2006) Parallel-Redrawing Mechanisms, Pseudo-Triangulations and Kinetic Planar Graphs. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 421-433 (Official URL: http://dx.doi.org/10.1007/11618058_38).

Full text not available from this repository.

Abstract

We study parallel redrawing graphs: graphs embedded on moving point sets in such a way that edges maintain their slopes all throughout the motion. The configuration space of such a graph is of an oriented-projective nature, and its combinatorial structure relates to rigidity theoretic parameters of the graph. A special type of kinetic structure emerges, whose events can be analyzed combinatorially. Of particular interest are those planar graph s which maintain non-crossing edges throughout the motion. Our main result is that they are (essentially) pseudo-triangulation mechanisms. These kinetic graph structures have potential applications in morphing of more complex shapes than just simple polygons.

Item Type:Conference Paper
Additional Information:10.1007/11618058_38
Classifications:M Methods > M.200 Animation
ID Code:708

Repository Staff Only: item control page

References

Pankaj Agarwal, Julien Basch, Leonidas Guibas, John Hershberger, and Li Zhang.: Deformable free space tilings for kinetic collision detection. International Journal of Robotics Research, 21:179-197, March 2003. Preliminary version appeared in Proc. 4th International Workshop on Algorithmic Foundations of Robotics (WAFR), 2000.

Oswin Aichholzer, Günter Rote, Bettina Speckmann, and Ileana Streinu.: The zig-zag path of a pseudo-triangulation. Proc. 8th International Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science 2748, pages 377-388, Ottawa, Canada, 2003. Springer Verlag.

Sergei Bespamyatnikh.: Enumerating pseudo-triangulations in the plane. Comput. Geom. Theory Appl., 30(3):207-222, 2005.

Jürgen Bokowski, Susanne Mock, and Ileana Streinu.: The folkman-lawrence topological representation theorem for oriented matroids - an elementary proof in rank 3. European Journal of Combinatorics, 22:601-615, July 2001.

Craig Gotsman and Vitaly Surazhsky. Guaranteed intersection-free polygon morphing. Computers and Graphics, 25(1):67-75, 2001.

Jack Graver, Brigitte Servatius, and Herman Servatius.: Combinatorial Rigidity. Graduate Studies in Mathematics vol. 2. American Mathematical Society, 1993.

Leonidas Guibas, John Hershberger, and Subash Suri.: Morphing simple polygons. Discrete and Computational Geometry, 24:1-34, 2000.

Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, and Walter Whiteley.: Planar minimally rigid graphs and pseudo-triangulations. Computational Geometry: Theory and Applications, pages 31-61, May 2005.

Audrey Lee, Ileana Streinu, and Louis Theran.: Finding and maintaining rigid components. Proc. Canad. Conf. Comp. Geom., Windsor, Canada, August 2005.

Michel Pocchiola and Gert Vegter.: Topologically sweeping visibility complexes via pseudo-triangulations. Discrete & Computational Geometry, 16(4):419-453, Dec. 1996.

Günter Rote, Francisco Santos, and Ileana Streinu. Expansive motions and the polytope of pointed pseudo-triangulations Janos Pach, Boris Aronov, Saugata Basu and Micha Sharir, editors, Discrete and Computational Geometry - The Goodman-Pollack Festschrift, Algorithms and Combinatorics, pages 699-736. Springer Verlag, Berlin, 2003.

Bettina Speckmann and Csaba Toth.: Allocating vertex pi-guards in simple polygons via pseudo-triangulations.

Proc. ACM-SIAM Symp. Discrete Algorithms (SODA), pages 109-118, 2003. To appear in Discrete and Computational Geometry, 2004.

Jorge Stolfi.: Oriented Projective Geometry: A Framework for Geometric Computations. Academic Press, New York, NY, 1991.

Ileana Streinu.: A combinatorial approach to planar non-colliding robot arm motion planning. IEEE Symposium on Foundations of Computer Science, pages 443-453, 2000.

Ileana Streinu.: Pseudo-triangulations, rigidity and motion planning. Discrete and Computational Geometry, to appear, 2005. A preliminary version appeared in Ileana Streinu.: A combinatorial approach to planar non-colliding robot arm motion planning

Walter Whiteley.: Some matroids from discrete applied geometry. J. Oxley J. Bonin and B. Servatius, editors, Matroid Theory, volume 197 of Contemporary Mathematics, pages 171-311. American Mathematical Society, 1996.