Efficient Computation of the Outer Hull of a Discrete Path

Autor:	Srečko Brlek, Jerome Tremblay, Romaine Weber, Hugo Tremblay
Rok vydání:	2014
Předmět:	Discrete mathematics Convex hull Chain code Intersection Computation Hull Path (graph theory) Data structure Time complexity Algorithm Mathematics
Zdroj:	Advanced Information Systems Engineering ISBN: 9783642387081 DGCI
DOI:	10.1007/978-3-319-09955-2_11
Popis:	We present here a linear time and space algorithm for computing the outer hull of any discrete path encoded by its Freeman chain code. The basic data structure uses an enriched version of the data structure introduced by Brlek, Koskas and Provencal: using quadtrees for representing points in the discrete plane ℤ×ℤ with neighborhood links, deciding path intersection is achievable in linear time and space. By combining the well-known wall follower algorithm for traversing mazes, we obtain the desired result with two passes resulting in a global linear time and space algorithm. As a byproduct, the convex hull is obtained as well.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::2a0ba2501d244d2aed154df931330cc1 https://doi.org/10.1007/978-3-319-09955-2_11 Zobrazit plný text záznamu