Linear time and space algorithms for discrete paths on the 1-uniform regular lattices of Z2

In 2009, Brlek, Koskas and Provençal proposed a data structure allowing self-intersection detection of discrete paths in linear time and space in the worst case. However, their ideas do not apply in a straightforward manner to arbitrary lattices. We propose an extension of their results to lattices of Z2 whose adjacency relation is between points at distance one with respect to the uniform norm.