Optimal parallel algorithm for finding the smallest enclosing rectangle on a mesh-connected computer

Chang Sung Jeong, Jung Ju Choi

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

Abstract

In this paper, we consider the problem of finding the smallest triangle circumscribing a convex polygon with n edges. We shall show that this can be done in O(√n) time by the efficient data partition schemes and the proper set mapping and comparison operations using what so called √n-decomposition technique. Since the nontrivial operation on MCC requires Ω(√n), the time complexity is optimal within constant time factor.

Original languageEnglish
Title of host publicationProceedings of the International Conference on Parallel Processing
PublisherPubl by IEEE
Pages138-141
Number of pages4
ISBN (Print)0818626720
Publication statusPublished - 1992
Externally publishedYes
EventProceedings of the 6th International Parallel Processing Symposium - Beverly Hills, CA, USA
Duration: 1992 Mar 231992 Mar 26

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

OtherProceedings of the 6th International Parallel Processing Symposium
CityBeverly Hills, CA, USA
Period92/3/2392/3/26

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Optimal parallel algorithm for finding the smallest enclosing rectangle on a mesh-connected computer'. Together they form a unique fingerprint.

Cite this