@inproceedings{b9359151fce44b4994e44bc78a996ec4,

title = "Local versus non-local computation of length of digitized curves",

abstract = "We consider the problem of computing the length of a curve from digitized versions of the curve using parallel computation. Our aim is to study the inherent parallel computational complexity of this problem as a function of the digitization level. Precise formulations for the digitization, the parallel computation, and notions of local and nonlocal computations are given. We show that length cannot be computed locally from digitizations on rectangular tesseUations. However, for a random tessellation and appropriate deterministic ones, we show that the length of straight line segments can be computed locally.",

author = "Kulkarni, {S. R.} and Mitter, {S. K.} and Richardson, {T. J.} and Tsitsiklis, {J. N.}",

note = "Funding Information: * This work was supported in part by the U.S. Army Research Office under Contract DAAL03-86-K-0171, by the Dept. of the Navy under Air Force Contract F19628-90-C-0002, and by the National Science Foundation under contract ECS-8552419. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 13th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1993 ; Conference date: 15-12-1993 Through 17-12-1993",

year = "1993",

doi = "10.1007/3-540-57529-4_45",

language = "English (US)",

isbn = "9783540575290",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "94--103",

editor = "Shyamasundar, {Rudrapatna K.}",

booktitle = "Foundations of Software Technology and Theoretical Computer Science - 13th Conference, Proceedings",

address = "Germany",

}