Search

A pseudo-triangulation is a planar subdivision into polygons with three convex vertices, useful for ray shooting, visibility problems and kinetic collision detection. As pseudo-triangulations are quite young, there is a lack of specialized algorithms for them. In this paper, we address the question of location in pseudo-triangulations. We propose two location algorithms based on the so-called stochastic walk and present their experimental results. The class of walk location algorithms is very popular for triangulations, namely in engineering applications, due to simplicity and low memory requirements, in spite of their non-optimality. As far as we know, no walk algorithm specialized on pseudo-triangulations has been developed before.

A pseudo-triangulation is a planar subdivision into pseudo triangles - polygons with three convex vertices, used mainly in motion planning problems in robotics. As it is a rather new concept, not too many algorithms to construct it exist. In this paper, we propose an online version of incremental insertion, with generalized flips to improve the shape of pseudo-triangles. This algorithmic paradigm is often used for Delaunay triangulations, but for pseudo-triangulations it has been used only in an off-line version (for sorted input points). We also experimented with several optimization criteria for the flips and show their influence on the shape of pseudo-triangles.