Local versus non-local computation of length of digitized curves

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 13th Conference, Proceedings
EditorsRudrapatna K. Shyamasundar
PublisherSpringer Verlag
Pages94-103
Number of pages10
ISBN (Print)9783540575290
DOIs
StatePublished - 1993
Event13th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1993 - Bombay, India
Duration: Dec 15 1993Dec 17 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume761 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1993
CountryIndia
CityBombay
Period12/15/9312/17/93

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Local versus non-local computation of length of digitized curves'. Together they form a unique fingerprint.

  • Cite this

    Kulkarni, S. R., Mitter, S. K., Richardson, T. J., & Tsitsiklis, J. N. (1993). Local versus non-local computation of length of digitized curves. In R. K. Shyamasundar (Ed.), Foundations of Software Technology and Theoretical Computer Science - 13th Conference, Proceedings (pp. 94-103). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 761 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-57529-4_45