A linear time and space algorithm for detecting path intersection in \(\mathbb Z^d\)
From MaRDI portal
Publication:638566
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
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\)