References for Pseudo-Triangulation Workshop in Barbados

A. Visibility Complex
B. Kinetic Data Structures
C. Rigidity Theory
D. Triangulations
E. Implementations
F. Other


A. Visibility Complex

Pseudo-triangulations have been introduced in these papers, as tilings of the free space of a finite set of smooth convex obstacles in the plane, and applied to the visibility complexe.

  1. P. Angelier and M. Pocchiola. A 'sum of squares' theorem for visibility complexes (extended abstract).
    sos.ps.gz

  2. M.Pocchiola, G.Vegter. Pseudo Triangulations: Theory and Applications 1996
    pv-ptta-96.ps

  3. M.Pocchiola, G.Vegter. Computing Visibility Graphs via Pseudo Triangulations 1995
    liens-95-15.A4.ps.Z

  4. M.Pocchiola. Horizon Trees versus Pseudo Triangulations
    In European Workshop on Computational Geometry, March 1997
    pocchiola.ps(Talk Summary)

  5. M.Pocchiola, G.Verter. Topologically Sweeping Visibility Complexes via Pseudo Triangulations
    Discrete Computational Geometry 16:419-453, December 1996
    16n4p419.pdf

  6. Other publications of M.Pocchiola
    http://www.dmi.ens.fr/users/pocchiol/Pocchiola.html

B. Kinetic Data Structures

The Kinetic Data structures community is using pseudo-triangulations for polygonal obstacles. See papers 1, 2, 8 below. I added the others to the list because they introduce the KDS framework (3,4,5, 6) or because there is some technique there that I found interesting (7).
  1. David Kirkpatrick and Bettina Speckmann, Separation sensitive Kinetic Collision Detection for Simple Polygons,
    Japan Conference on Computational Geometry, Nov. 2000.
    pdf, citeseer.

  2. P.Agarwal, J.Basch, L.Guibas, J.Hershberger, L.Zhang. Deformable Space Tilings for Kinetic Collision Detection.
    4th International Workshop on Algorithmic Foundations of Robotics, 2000.
    pdf, citeseer.

  3. Julian Basch. Kinetic Data Structures.
    PhD Thesis, ps.gz.

  4. J.Basch, L.Guibas, C.Silverstein, L.Zhang. A Practical Evaluation of Kinetic Data Structures. 1997
    pdf, citeseer.

  5. J.Basch, J.Comba, L.Guibas, J.Hershberger, C.Silverstein, L.Zhang.
    Kinetic Data Structures: Animating Proofs Through Time.
    Symposium on Computational Geometry, June 1999. p.427-428
    pdf, citeseer.

  6. J.Basch, L.Guibas, J.Hershberger. Data Structures for Mobile Data.
    pdf, citeseer

  7. L.Guibas, M.Karavelas. Interval Methods for Kinetic Simulations
    pdf, from Menelaos publications and talks.

  8. D.Kirkpatrick, J.Snoeyink and B.Speckmann. Kinetic Collision Detection for Simple Polygons.
    ps, from Bettina's publication list.


C. Rigidity Theory

Rigidity theoretic properties of minimum pseudo triangulations, and application to the Carpenter's Rule Problem (1). This paper has to be read in conjunction with (2).
  1. I.Streinu. A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning
    motion.ps.gz

  2. R. Connelly, E. Demaine and G. Rote, Straightening Polygonal Arcs and Convexifying Polygonal Cycles
    in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), Redondo Beach, California, November 12-14, 2000, pages 432-442.
    Get it from Erik's page OR get the extended version(in ps format) from Guenter Rote's Page.


D. Triangulations

I added these papers because I like or I am intrigued by them. I think they can be useful for us. E.g. Sergey's paper for enumerating triangulations has an elegant technique which extends to pseudo triangulations. Edelman and Reiner simply intrigues me. I do not understand clearly its connection with visibility, but maybe some of you do.

I would like to add more here, but I do not have time. I think that many natural questions about triangulations can be asked for pseudo triangulations. So please add to the list (and bring a copy to the workshop) your favorite papers on triangulations.

  1. S.Bespamyatnikh. An efficient algorithm for enumeration of triangulations.
    cgw.ps.gz (Not full version)

  2. P. H. Edelman and V. Reiner. Visibility Complexes and the Baues Problem for Triangulations in the Plane.
    Discret Comput. Geometry 20:35-59, 1998
    20n1p35.pdf

  3. Oswin Aichholzer, Franz Aurenhammer, Michael Taschwer and Guenter Rote, Triangulations Intersect Nicely, Proc.
    11th SoCG, Vancouver 1995, pp. 220-229.
    This is the journal version (in ps format) from Guenter Rote's Page


E. Implementations

These are self explanatory.

  1. Greedy Flip Algorithm in Action. M.Pocchiola, G. Vegter
    http://www.di.ens.fr/~gecoal/gfaa/gfaa.html

  2. DemoKin - Demonstration of Kinetic Data Structures
    http://www-graphics.stanford.edu/~jbasch/demokin

  3. Flipping pseudo-triangles: Jack has a very rudimentary applet that allows you to create a point set, compute a canonical pseudo-triangulation, and then select edges to flip.
    http://www.cs.unc.edu/~snoeyink/demos/pseudotri/

F. Other

This is self-explanatory. More combinatorial properties of pseudo triangulations wait to be discovered.

  1. Lutz Kettner,Andrea Mantler, Jack Snoeyink, Bettina Speckmann and Fumihiko Takeuchi.
    Bounded degree pseudo triangulations  paper.pdf