A linear time and space algorithm for detecting path intersection in Z^d

DOI10.1016/J.TCS.2011.04.019MaRDI QIDQ638566zbMATH OpenOpenAlexFDO

Authors 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

Freeman codelattice pathsradix treeself-intersection

Mathematics Subject Classification ID

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

Recommendations

• A linear time and space algorithm for detecting path intersection
• Linear time and space algorithms for discrete paths on the 1-uniform regular lattices of \(\mathbb{Z}^2\)
• Efficient Computation of the Outer Hull of a Discrete Path
• Efficient operations on discrete paths
• Parallel, overlapped, and intersected digital straight lines

Cites work

• A linear time and space algorithm for detecting path intersection
• Combinatorial View of Digital Convexity
• Detection of the discrete convexity of polyominoes
• Developments in Language Theory
• scientific article; zbMATH DE number 4211555 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• Lyndon + Christoffel = digitally convex
• On the tiling by translation problem
• Polygonal representations of digital sets
• PROPERTIES OF THE CONTOUR PATH OF DISCRETE SETS
• Quad trees: A data structure for retrieval by composite keys
• Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
• What does digital straightness tell about digital convexity?

Cited in

(6)

• 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\)
• Efficient operations on discrete paths
• A linear time and space algorithm for detecting path intersection
• Combinatorial properties of double square tiles
• A parallelogram tile fills the plane by translation in at most two distinct ways

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q638566)