Home // ADVCOMP 2011, The Fifth International Conference on Advanced Engineering Computing and Applications in Sciences // View article

Hybrid Walking Point Location Algorithm

Authors:
Roman Soukal
Martina Málková
Tomáš Vomáčka
Ivana Kolingerová

Keywords: Algorithm design and analysis; Computational geometry; Computer graphics

Abstract:
Finding which triangle in a planar triangular mesh contains a query point (so-called point location problem) is one of the most frequent tasks in computational geometry. Therefore, using an algorithm with the lowest possible complexity is appropriate. However, such complexity may be achieved only by using additional data structures, leading into algorithms that are more difficult to implement and have additional memory demands. A possible solution is to use walking algorithms, which are easier to implement. They either do not require any additional memory, or require only a small portion of it in order to achieve the lowest possible complexity as well. In this paper, we propose a new walking algorithm combining two existing approaches to provide speed, robustness and easy implementation, and compare it with the fastest representatives of walking algorithms. Experiments proved that our algorithm is faster than the fastest existing visibility and straight walk algorithms, and depending on the character of input data, either as fast as the orthogonal walk algorithms or faster.

Pages: 7 to 12

Copyright: Copyright (c) IARIA, 2011

Publication date: November 20, 2011

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-172-4

Location: Lisbon, Portugal

Dates: from November 20, 2011 to November 25, 2011