A linear time and space algorithm for detecting path intersection in \(\mathbb Z^d\)

DOI10.1016/j.tcs.2011.04.019zbMath1234.68439MaRDI QIDQ638566

Michel Koskas, Xavier Provençal, Srečko Brlek

Publication date: 12 September 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.019

zbMATH Keywords

lattice paths; self-intersection; Freeman code; radix tree

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R05: Combinatorics in computer science

68R15: Combinatorics on words

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P05: Data structures

Related Items

Efficient operations on discrete paths, Combinatorial properties of double square tiles, A parallelogram tile fills the plane by translation in at most two distinct ways, An optimal algorithm to generate extendable self-avoiding walks in arbitrary dimension, Linear time and space algorithms for discrete paths on the 1-uniform regular lattices of \(\mathbb{Z}^2\)

Cites Work

• Lyndon + Christoffel = digitally convex
• On the tiling by translation problem
• Quad trees: A data structure for retrieval by composite keys
• Detection of the discrete convexity of polyominoes
• Polygonal representations of digital sets
• Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
• A Linear Time and Space Algorithm for Detecting Path Intersection
• What Does Digital Straightness Tell about Digital Convexity?
• Combinatorial View of Digital Convexity
• Developments in Language Theory
• PROPERTIES OF THE CONTOUR PATH OF DISCRETE SETS
• Unnamed Item
• Unnamed Item
• Unnamed Item