Simplex Transversal in a Linked Simplex Mesh

Intro

The idea is to transverse the mesh or part of the mesh in linear time. In simple cases this is easily achieved. However the algorithm has to remember which simplexes have already been transversed. I realized the issue when I did not get linear transversal as storing the previously visited simplexes creates a tree which has log lookup time.

Note however that the general transversal can be done in linear time using hash tables to remember visited simplexes.

General Transversal

Consider a linked simplex mesh where every simplex has a unique id. To transverse the mesh from an initial simplex s.

Let dead be a list of dead or visited simplexes.
Let process be a list of simplexes to be processed.

transverse(s)
    for i = 0..n-1
        if ( hasVisited(ni[i])==false )
            dead.push(i)
            process.push(i)


If the hasVisited stores each visited simplex in an ordered list this has log access time. However hash tables could be used yielding linear access time and hence the generalized linear transversal could be avoided. The hash table is fiddly as it needs to always be adjusted to the size of the number of simplexes transversed. ie is linearly dependent on the number of simplexes.

General Linear Transversal

This can be achieved at the expense of memory.

From the linked simplex data structure derive a linked simplex with a boolean value with each of its neighbors that represents if the link has been transversed or not.

Defining this new data structure.

Linked Simplex with Memory Transversal.
Let n be the dimension of the simplex.
Let pi[n] be its points
Let ni[n] be its neighbors
Let nib[n] be the flags indicating if the link has been transversed.

Define some supporting operators to reset all a simplexes memory traversals to false.

nibreset()
    for i = 0..n-1
        nib[i] = false

Define a switch to turn on memory transversal. Both paths are turned on.

nibtrans(i)
    if (nib[i])
        Let x be vi[ni[i]]
        x.nib[ x.niInverse( ni[i] ) ] = true
        nib[i] = true
   

Note that the local link and the links memory transversal have the same local index as they are associated with each other.

Reconsider the transverse(s) function with the new LSMT data structure. Notice that it is simpler to transverse the mesh as only one vector is now being used instead of two. ie instead of process and dead vectors only one is needed.

Reset the links to untransversed.
Let dead be a stack of transversed links.
Let n be the dimension.
Let s be the initial simplex.

transvers(s)
    for i = 0..n-1
        if (s.ni[i]==0)
            continue
        if (s.nib[i]==false)
            dead.push(s.ni[i])
            s.nibtrans(i)


Reset dead traversals after wards.

for i = 0..dead.size()-1
    dead[i].nibreset()

One Mesh Linear Transversal

When there is only one mesh then simply transverse vi the list of simplexes for transversal in linear time.

This is however global processing of the simplexes. So it is not general in that if only a small number of simplexes are being considered why transverse every simplex in the mesh?