by Bhowmick, P, Pal, O and Klette, R
Abstract:
We propose an algorithm to generate random digital curves of finite length, generating points of a digital path ρ on the fly. Path ρ never intersects or touches itself, and hence becomes simple and irreducible. This is ensured by detecting every possible trap formed by the previously generated part of ρ, which, if entered into, cannot be exited without touching or intersecting ρ. The algorithm is completely free of any backtracking and its time complexity is linear in the length of ρ. Implemented and tested exhaustively, it shows that it produces results as specified by the user. © 2010 IEEE.
Reference:
A linear-time algorithm for the generation of random digital curves (Bhowmick, P, Pal, O and Klette, R), In Proceedings – 4th Pacific-Rim Symposium on Image and Video Technology, PSIVT 2010, 2010.
Bibtex Entry:
@inproceedings{bhowmick2010acurves,
author = "Bhowmick, P and Pal, O and Klette, R",
booktitle = "Proceedings - 4th Pacific-Rim Symposium on Image and Video Technology, PSIVT 2010",
pages = "168--173",
title = "A linear-time algorithm for the generation of random digital curves",
year = "2010",
abstract = "We propose an algorithm to generate random digital curves of finite length, generating points of a digital path ρ on the fly. Path ρ never intersects or touches itself, and hence becomes simple and irreducible. This is ensured by detecting every possible trap formed by the previously generated part of ρ, which, if entered into, cannot be exited without touching or intersecting ρ. The algorithm is completely free of any backtracking and its time complexity is linear in the length of ρ. Implemented and tested exhaustively, it shows that it produces results as specified by the user. © 2010 IEEE.",
doi = "10.1109/PSIVT.2010.35",
isbn = "9780769542850",
language = "eng",
}