6 Conclusions

We have shown how to efficiently maintain free space pseudo-triangulations for points, as well as convex and simple polygons moving around in the plane. In addition to collision detection, the pseudo-triangulation structure provides a simple way for walking around the free space and performing operations such as ray shooting and other visibility queries. Unlike any previous collision detection method, our deformable tiling can be adapted to work for deformable objects, thus enabling new applications where simulation of flexible shapes is important. An extension of our ideas to 3D presents the next obvious challenge.