A linear time and space algorithm for detecting path intersection in Zd

S Brlek, M Koskas, X Provençal - Theoretical Computer Science, 2011 - Elsevier
S Brlek, M Koskas, X Provençal
Theoretical Computer Science, 2011Elsevier
The Freeman chain code is a common and useful way for representing discrete paths by
means of words such that each letter encodes a step in a given direction. In the discrete
plane Z2 such a coding is widely used for representing connected discrete sets by their
contour which forms a closed and intersection free path. In this paper, we use a
multidimensional radix tree like data structure for storing paths in the discreted-dimensional
space Zd. It allows to design a simple and efficient algorithm for detecting path intersection …
The Freeman chain code is a common and useful way for representing discrete paths by means of words such that each letter encodes a step in a given direction. In the discrete plane Z2 such a coding is widely used for representing connected discrete sets by their contour which forms a closed and intersection free path. In this paper, we use a multidimensional radix tree like data structure for storing paths in the discreted-dimensional space Zd. It allows to design a simple and efficient algorithm for detecting path intersection. Even though an extra initialization is required, the time and space complexities remain linear for any fixed dimension d. Several problems that are solved by adapting our algorithm are also discussed.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果