### 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 language | English (US) |
---|---|

Title of host publication | Foundations of Software Technology and Theoretical Computer Science - 13th Conference, Proceedings |

Editors | Rudrapatna K. Shyamasundar |

Publisher | Springer Verlag |

Pages | 94-103 |

Number of pages | 10 |

ISBN (Print) | 9783540575290 |

DOIs | |

State | Published - 1993 |

Event | 13th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1993 - Bombay, India Duration: Dec 15 1993 → Dec 17 1993 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 761 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 13th Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1993 |
---|---|

Country | India |

City | Bombay |

Period | 12/15/93 → 12/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

*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