Patent ID: 8373716

Claim:
A method for parallel approximation of distance maps on a discrete representation of a single manifold, the method comprising: determining a plurality of characteristics of the manifold; applying a plurality of Euclidean grids over the manifold according to said characteristics; for each Euclidean grid applied on the discrete representation of a manifold, iterating over rows of said Euclidean grid in a first direction; and for each row currently visited during said iterating in said first direction, calculating a distance value using a Graphical Processing Unit (GPU) for each single cell of said currently visited row in parallel, wherein said calculating is carried out according to a predefined approximation rule, using a distance value calculated for each one of respective cells of a single row visited immediately before said currently visited row, wherein said cells of said single row visited before said currently visited row are adjacent to said single cell in said Euclidean grid; and determining the distance map according to said plurality of Euclidean grids.