Pseudo-Triangulations


Pseudo-triangulations, and the closely related geodesic triangulations, have been used in Computational Geometry in ray shooting, visibility and kinetic data structures.

My interest is mainly in the special minimum or pointed pseudo-triangulations, which I have introduced in my paper A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning (see FOCS 2000 extended abstract ) to give an algorithmic solution to the Carpenter's Rule Problem. They have remarkable combinatorial and rigidity-theoretic properties, many more awaiting to be discovered.

Here's some of the ongoing research in this direction.