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

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.

- P. Angelier and M. Pocchiola.
A 'sum of squares' theorem for visibility complexes (extended
abstract).

sos.ps.gz

- M.Pocchiola, G.Vegter. Pseudo Triangulations: Theory and Applications 1996

pv-ptta-96.ps

- M.Pocchiola, G.Vegter. Computing Visibility Graphs via Pseudo Triangulations 1995

liens-95-15.A4.ps.Z

- M.Pocchiola. Horizon Trees versus Pseudo Triangulations

In European Workshop on Computational Geometry, March 1997

pocchiola.ps(Talk Summary)

- M.Pocchiola, G.Verter. Topologically Sweeping Visibility Complexes
via Pseudo Triangulations

Discrete Computational Geometry 16:419-453, December 1996

16n4p419.pdf

- Other publications of M.Pocchiola

http://www.dmi.ens.fr/users/pocchiol/Pocchiola.html

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).

- David Kirkpatrick and Bettina Speckmann,
Separation sensitive Kinetic Collision Detection
for Simple Polygons,

Japan Conference on Computational Geometry, Nov. 2000.

pdf, citeseer.

- 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.

- Julian Basch. Kinetic Data Structures.

PhD Thesis, ps.gz.

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

pdf, citeseer.

- 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.

- J.Basch, L.Guibas, J.Hershberger. Data Structures for Mobile Data.

pdf, citeseer

- L.Guibas, M.Karavelas. Interval Methods for Kinetic Simulations

pdf, from Menelaos publications and talks.

- D.Kirkpatrick, J.Snoeyink and B.Speckmann. Kinetic Collision Detection for Simple
Polygons.

ps, from Bettina's publication list.

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).

- I.Streinu. A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning

motion.ps.gz - 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.

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.

- S.Bespamyatnikh. An efficient algorithm for enumeration of triangulations.

cgw.ps.gz (Not full version)

- 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

- 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

These are self explanatory.

- Greedy Flip Algorithm in Action. M.Pocchiola, G. Vegter

http://www.di.ens.fr/~gecoal/gfaa/gfaa.html

- DemoKin - Demonstration of Kinetic Data Structures

http://www-graphics.stanford.edu/~jbasch/demokin

- 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/

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

- Lutz Kettner,Andrea Mantler, Jack Snoeyink, Bettina Speckmann and Fumihiko Takeuchi.

Bounded degree pseudo triangulations paper.pdf