Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Résumé

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