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.
- 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
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).
- 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.
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).
- 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.
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.
- 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
E. Implementations
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/
F. Other
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