EFFICIENT PARALLEL RANGE SEARCHING AND PARTITIONING ALGORITHMS*

References

• Andrews , H. C. , Introduction to Mathematical Techniques in Pattern Recognition. WileyInterscience , New York , 1972 .
   Google Scholar
• Avis , D. ( 1986 ). Diameter partitioning , Discrete Comput Geom., , 1 , 265 – 276 .
   Web of Science ®Google Scholar
• Asano , T. , Bhattacharya , B. , Keil , M. and Yao , F. ( 1988 ). Clustering algorithms based on minimum and maximum spanning trees, Proc. 4th ACM Symp. on. Compo Geom , pp. 252 – 257 .
   Google Scholar
• Cole , R. (1988). Parallel merge sort, SIAM J. Comput. , 17, 770–785.
   Web of Science ®Google Scholar
• Chandran , S. , Kim , S. K. and Mount , D. M. ( 1992 ). Parallel computational geometry of rectangles , Algorithmica , 7 , 25 – 49 .
   Google Scholar
• Drezner , Z. ( 1987 ). On the rectangular p-center problem , Naval Res. Logist. , 34 , 229 – 234 .
   Google Scholar
• Goodrich , M. T. ( 1991 ). Intersecting line segments in parallel with an output-sensitive number of processors , SIAM J. Comput. , 20 , 737 – 755 .
   Google Scholar
• Garey , M. R. and Johnson , D. S. , Computers and Intractability: A Guide to the Theory of NP-Completeness , Freeman, San Fransisco , 1972 .
   Google Scholar
• Guha S. ( 1989 ). An O(n) time set bipartition algorithm under the L∞ metric, Manuscript, EECS Department, University of Michigan, Ann Arbor , MI 48109-2122 .
   Google Scholar
• Hershberger , J. and Suri , S. ( 1991 ). Finding tailored partitions , J. Algorithms , 12 , 431 – 463 .
   Google Scholar
• Johnson , D. S. ( 1982 ). The NP-completeness column , J. Algorithms , Vol. 3 .
   Google Scholar
• Jaja , J. , An introduction to Parallel Algorithms , Addison-Wesley, 1992 .
   Google Scholar
• Monma , C. and Suri . S. , Partitioning points and graphs to minimize the maximum or the sum of diameters, Proceedings, Sixth International Conference on the Theory and Applications of Graphs, , Wiley , New York , 1989 .
   Google Scholar
• Preparata , F. P. and Shamos , M. I. , Computational Geometry: An Introduction , SpringerVerlag, New York , 1985 .
   Google Scholar
• *This work was partially supported by a Research Launching Grant of the Faculty of Engineering and Mathematical Sciences, University of Western Australia.
   Google Scholar