Serial and parallel algorithms for the medial axis transform

John Jenq, Sartaj Sahni

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the International Conference on Parallel Processing
PublisherPubl by IEEE
Pages326-333
Number of pages8
ISBN (Print)0818626720
StatePublished - 1 Dec 1992
EventProceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA
Duration: 23 Mar 199226 Mar 1992

Other

OtherProceedings of the 6th International Parallel Processing Symposium
CityBeverly Hills, CA, USA
Period23/03/9226/03/92

Fingerprint

Medial Axis Transform
Parallel algorithms
Parallel Algorithms
Hypercube
Perimeter

Cite this

Jenq, J., & Sahni, S. (1992). Serial and parallel algorithms for the medial axis transform. In Proceedings of the International Conference on Parallel Processing (pp. 326-333). Publ by IEEE.
Jenq, John ; Sahni, Sartaj. / Serial and parallel algorithms for the medial axis transform. Proceedings of the International Conference on Parallel Processing. Publ by IEEE, 1992. pp. 326-333
@inproceedings{7b796e3d91d842cdb62313b9e8c715a6,
title = "Serial and parallel algorithms for the medial axis transform",
abstract = "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.",
author = "John Jenq and Sartaj Sahni",
year = "1992",
month = "12",
day = "1",
language = "English",
isbn = "0818626720",
pages = "326--333",
booktitle = "Proceedings of the International Conference on Parallel Processing",
publisher = "Publ by IEEE",

}

Jenq, J & Sahni, S 1992, Serial and parallel algorithms for the medial axis transform. in 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.

Proceedings of the International Conference on Parallel Processing. Publ by IEEE, 1992. p. 326-333.

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-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 -

Jenq J, Sahni S. Serial and parallel algorithms for the medial axis transform. In Proceedings of the International Conference on Parallel Processing. Publ by IEEE. 1992. p. 326-333