Walking algorithms

Written by Roman Soukal

Roman Soukal

University of West Bohemia

Seminar in Czech
March 11, 2009 at 9:30
University of West Bohemia, UK417


presentation slides (1.5MB PPT)


(download in PDF)

For triangulated data in 2D and 3D including pseudotriangulations in 2D, a location problem usually means how to find a triangle, tetrahedron or pseudotriangle which contains the given point. Many efficient algorithms and data structures exist which are suitable for planar or tetrahedral meshes, such as DAGs (directed acyclic graphs), buckets, quadtrees or octrees, skip lists, data structures based on random sampling, etc. These methods mostly work in O(log n) expected or worst-case time per one location query. Unfortunately, memory requirements of location data structures, although usually O(n), may be for large data prohibitive. Therefore, time-suboptimal approaches utilizing walk algorithms (O(n1/3) up to O(n1/2)), have been developed and are used because no extra location data structures are needed and so no extra memory is consumed. This is the main advantage of walking algorithms.

[ Back ]

Copyright © 2013 Centre of Computer Graphics and Visualization. All Rights Reserved.