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

DOI10.1016/j.tcs.2011.04.019zbMath1234.68439OpenAlexW2120324771MaRDI 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 pathsself-intersectionFreeman coderadix tree

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Combinatorics on words (68R15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (5)

Efficient operations on discrete paths ⋮ Combinatorial properties of double square tiles ⋮ 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\) ⋮ A parallelogram tile fills the plane by translation in at most two distinct ways

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A linear time and space algorithm for detecting path intersection in \(\mathbb Z^d\)