Efficient operations on discrete paths

详细信息    查看全文

• 作者：Alexandre Blondin Massé ; Srečko Brlek ; ^{brlek.srecko@uqam.ca" class="auth_mail" title="E-mail the corresponding author} ; Hugo Tremblay
• 关键词：Freeman code ; Lattice paths ; Radix tree ; Discrete sets ; Outer hull ; Convex hull ; Polyomino intersection ; Union ; Complement ; Difference
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：18 April 2016
• 年：2016
• 卷：624
• 期：Complete
• 页码：121-135
• 全文大小：516 K

文摘

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$\mathbb{Z}\times \mathbb{Z}$ augmented with neighborhood links, which was introduced in particular to decide in linear time if a discrete path is self-intersecting.