Efficient operations on discrete paths

DOI10.1016/j.tcs.2015.07.033zbMath1417.68229OpenAlexW1051752637MaRDI QIDQ265059

Hugo Tremblay, Srečko Brlek, Alexandre Blondin Massé

Publication date: 1 April 2016

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

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

zbMATH Keywords

convex hulllattice pathsdiscrete setsouter hulldifferencecomplementFreeman codepolyomino intersectionradix treeunion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Polyominoes (05B50)

Related Items (2)

Linear time and space algorithms for discrete paths on the 1-uniform regular lattices of \(\mathbb{Z}^2\) ⋮ A measure of \(Q\)-convexity for shape analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial properties of double square tiles
• A linear time and space algorithm for detecting path intersection in \(\mathbb Z^d\)
• Lyndon + Christoffel = digitally convex
• An optimal convex hull algorithm in any fixed dimension
• Algorithms for polyominoes based on the discrete Green theorem
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• An efficient algorithm for determining the convex hull of a finite planar set
• Salient and reentrant points of discrete sets
• Efficient Computation of the Outer Hull of a Discrete Path
• A Combinatorial Lemma and Its Application to Probability Theory
• Factorizing words over an ordered alphabet
• Developments in Language Theory

This page was built for publication: Efficient operations on discrete paths