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

Efficient operations on discrete paths

Blondin Massé Alexandre, Brlek Srecko et Tremblay Hugo. (2016). Efficient operations on discrete paths. Theoretical Computer Science, 624, p. 121-135.

[thumbnail of polyomino-quadtree.pdf]
Prévisualisation
PDF - Version acceptée
395kB

URL officielle: http://dx.doi.org/doi:10.1016/j.tcs.2015.07.033

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.

Type de document:Article publié dans une revue avec comité d'évaluation
ISSN:03043975
Volume:624
Pages:p. 121-135
Version évaluée par les pairs:Oui
Date:2016
Identifiant unique:10.1016/j.tcs.2015.07.033
Sujets:Sciences naturelles et génie > Sciences mathématiques
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique
Mots-clés:freeman code, lattice paths, radix tree, discret sets, outer hull, convex hull, polyomino intersection, union, complement, difference
Déposé le:16 déc. 2020 20:11
Dernière modification:16 déc. 2020 20:11
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630