Details

Autor(en) / Beteiligte

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

Titel

Efficient operations on discrete paths

Ist Teil von

• Theoretical computer science, 2016-04, Vol.624, p.121-135

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2016

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We present linear time and space operations on discrete paths. First, we compute the outer hull of any discrete path. As a consequence, a linear time and space algorithm is obtained for computing the convex hull. Next, we provide a linear algorithm computing the overlay graph of two simple closed paths. From this overlay graph, one can easily compute the intersection, union and difference of two Jordan polyominoes, i.e. polyominoes whose boundary is a Jordan curve. The linear complexity is obtained by using an enriched version of a data structure introduced by Brlek, Koskas and Provençal: a quadtree for representing points in the discrete plane Z×Z augmented with neighborhood links, which was introduced in particular to decide in linear time if a discrete path is self-intersecting.