### Abstract

We develop an O(n^{2}) time serial algorithm to obtain the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log^{2} n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n^{2}) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an O(log n) time hypercube algorithm for both of these problems. Here n is the number of squares in the MAT and the algorithms use O(n^{2}) processors.

Original language | English |
---|---|

Title of host publication | Proceedings of the International Conference on Parallel Processing |

Publisher | Publ by IEEE |

Pages | 326-333 |

Number of pages | 8 |

ISBN (Print) | 0818626720 |

State | Published - 1 Dec 1992 |

Event | Proceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA Duration: 23 Mar 1992 → 26 Mar 1992 |

### Other

Other | Proceedings of the 6th International Parallel Processing Symposium |
---|---|

City | Beverly Hills, CA, USA |

Period | 23/03/92 → 26/03/92 |

### Fingerprint

### Cite this

*Proceedings of the International Conference on Parallel Processing*(pp. 326-333). Publ by IEEE.

}

*Proceedings of the International Conference on Parallel Processing.*Publ by IEEE, pp. 326-333, Proceedings of the 6th International Parallel Processing Symposium, Beverly Hills, CA, USA, 23/03/92.

**Serial and parallel algorithms for the medial axis transform.** / Jenq, John; Sahni, Sartaj.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

TY - GEN

T1 - Serial and parallel algorithms for the medial axis transform

AU - Jenq, John

AU - Sahni, Sartaj

PY - 1992/12/1

Y1 - 1992/12/1

N2 - We develop an O(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an O(log n) time hypercube algorithm for both of these problems. Here n is the number of squares in the MAT and the algorithms use O(n2) processors.

AB - We develop an O(n2) time serial algorithm to obtain the medial axis transform (MAT) of an n×n image. An O(log n) time CREW PRAM algorithm and an O(log2 n) time SIMD hypercube parallel algorithm for the MAT are also developed. Both of these use O(n2) processors. Two problems associated with the MAT are also studied. These are the area and perimeter reporting problem. We develop an O(log n) time hypercube algorithm for both of these problems. Here n is the number of squares in the MAT and the algorithms use O(n2) processors.

UR - http://www.scopus.com/inward/record.url?scp=0026971482&partnerID=8YFLogxK

M3 - Conference contribution

SN - 0818626720

SP - 326

EP - 333

BT - Proceedings of the International Conference on Parallel Processing

PB - Publ by IEEE

ER -