Local Versus Nonlocal Computation of Length of Digitized Curves

S. R. Kulkarni, S. K. Mitter, J. N. Tsitsiklis

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


In this paper, 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 tessellations. However, for a random tessellation and appropriate deterministic ones, we show that the length of straight line segments can be computed locally. Implications of our results for a method for image segmentation and a number of open problems are discussed.

Original languageEnglish (US)
Pages (from-to)711-718
Number of pages8
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number7
StatePublished - Jul 1994

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


  • Local
  • digitized curve
  • length
  • nonlocal
  • parallel computation


Dive into the research topics of 'Local Versus Nonlocal Computation of Length of Digitized Curves'. Together they form a unique fingerprint.

Cite this