The search functionality is under construction.

Keyword Search Result

[Keyword] farthest neighbors problem of polygons(1hit)

1-1hit
  • Designing Efficient Parallel Algorithms with Multi-Level Divide-and-Conquer

    Wei CHEN  Koichi WADA  

     
    PAPER

      Vol:
    E84-A No:5
      Page(s):
    1201-1208

    Multi-level divide-and-conquer (MDC) is a generalized divide-and-conquer technique, which consists of more than one division step organized hierarchically. In this paper, we investigate the paradigm of the MDC and show that it is an efficient technique for designing parallel algorithms. The following parallel algorithms are used for studying the MDC: finding the convex hull of discs, finding the upper envelope of line segments, finding the farthest neighbors of a convex polygon and finding all the row maxima of a totally monotone matrix. The third and the fourth algorithms are newly presented. Our discussion is based on the EREW PRAM, but the methods discussed here can be applied to any parallel computation models.