The stochastic walk algorithms for point location in pseudo-triangulations

摘要

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 triangula-tions, 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.