An optimal parallel algorithm for finding the smallest enclosing rectangle on a mesh-connected computer (for rectangle read triangle)

摘要

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