A Linear Time and Space Algorithm for Detecting Path Intersection

DOI10.1007/978-3-642-04397-0_34zbMath1261.68122OpenAlexW1859961853MaRDI QIDQ3648803

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

Publication date: 1 December 2009

Published in: Discrete Geometry for Computer Imagery (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04397-0_34

zbMATH Keywords

lattice pathsself-intersectionFreeman coderadix treedata structurediscrete figures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (1)

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

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
• Combinatorial View of Digital Convexity
• Developments in Language Theory
• PROPERTIES OF THE CONTOUR PATH OF DISCRETE SETS
• Unnamed Item
• Unnamed Item

This page was built for publication: A Linear Time and Space Algorithm for Detecting Path Intersection