Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm. (English) Zbl 0707.68040

Schieber, Baruch; Vishkin, Uzi

Discrete Appl. Math. 29, No. 1, 97-111 (1990).

Summary: A novel technique for proving lower bounds in parallel computation is presented. The technique is based on mapping any algorithm for the problem being considered to an algorithm for another problem, for which a good lower bound is known. The mapping is done by careful application of Ramsey-like arguments.
Specifically, we study the parallel complexity of the following problem. Given an input convex polygon \(P=(v_ 0,...,v_{n-1})\), where \((v_ i,v_{i+1})\) (the indices are taken modulo n) is an edge of P, for \(i=0,...,n-1\), find the nearest neighbor of each vertex \(v_ i\) of P. that is, find a vertex \(v_ j\), \(j\neq i\), \(0\leq j<n\), whose (Euclidean) distance from \(v_ i\) is minimal. We present a parallel algorithm for the problem which runs in O(log log n) time using n/log log n processors on a CRCW PRAM. We prove that \(\Omega\) (log log n) time is needed for solving the problem on a CRCW PRAM with O(n log\({}^ c n)\) processors, for any constant c.

MSC:

68W15	Distributed algorithms
05C35	Extremal problems in graph theory
68Q25	Analysis of algorithms and problem complexity
68Q05	Models of computation (Turing machines, etc.) (MSC2010)
68R10	Graph theory (including graph drawing) in computer science

Keywords:

lower bound; matching algorithm; parallel computation; parallel complexity; nearest neighbor; CRCW PRAM

References:

[1]	Aggarwal, A.; Chazelle, B.; Guibas, L.; O’Dunlaing, C.; Yap, C., Parallel computational geometry, Algorithmica, 3, 293-327 (1988) · Zbl 0664.68041
[2]	Atallah, M. J.; Goodrich, M. T., Efficient parallel solutions to geometric problems, J. Parallel and Distributed Comput., 3, 492-507 (1986)
[3]	Azar, Y.; Vishkin, U., Tight lower bounds on the complexity of parallel sorting, SIAM J. Comput., 16, 458-464 (1987) · Zbl 0654.68070
[4]	Borodin, A.; Hopcroft, J. E., Routing, merging, and sorting on parallel models of comparison, J. Comput. System Sci., 30, 130-145 (1985) · Zbl 0603.68065
[5]	Eppstein, D.; Galil, Z., Parallel algorithmic techniques for combinatorial computation, Annual Rev. Comput. Sci., 3, 233-283 (1988)
[6]	Fournier, A.; Kedem, Z., Comments on the All Nearest Neighbor problem for convex polygons, Inform. Process. Lett., 9, 105-107 (1979) · Zbl 0415.52002
[7]	Goodrich, M. T., Efficient parallel techniques for computational geometry, (Ph.D. Thesis (1987), Department of Computer Science, Purdue University: Department of Computer Science, Purdue University Lafayette, IN) · Zbl 0841.68121
[8]	Haggkvist, R.; Hell, P., Sorting and merging in rounds, SIAM J. Algebraic Discrete Methods, 3, 465-473 (1982) · Zbl 0493.68060
[9]	Karp, R. M.; Ramanchandran, V., A survey of parallel algorithms for shared memory machines, (Rept. UCB/CDS 88/408 (1988), Computer Science Division, University of California: Computer Science Division, University of California Berkeley, CA)
[10]	Kruskal, C. P., Searching, merging and sorting in parallel computation, IEEE Trans. Comput., 32, 942-946 (1983) · Zbl 0525.68039
[11]	Lee, D. T.; Preparata, F. P., The All Nearest Neighbor problem for convex polygons, Inform. Process. Lett., 7, 189-192 (1978) · Zbl 0387.52001
[12]	Maon, Y.; Schieber, B.; Vishkin, U., Parallel Ear Decomposition Search (EDS) and st-numbering in graphs, Theoret. Comput. Sci., 47, 277-298 (1986) · Zbl 0632.68066
[13]	Meyer auf der Heide, F.; Wigderson, A., The complexity of parallel sorting, Proceedings 26th Symposium on Foundations of Computer Science, 532-540 (1985)
[14]	Miller, G. L.; Ramachandran, V., A new triconnectivity algorithm and its parallelization, Proceedings 19th Symposium on Theory of Computing, 344-355 (1987)
[15]	Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer: Springer New York · Zbl 0759.68037
[16]	Schieber, B.; Vishkin, U., On finding lowest common ancestors: simplification and parallelization, SIAM J. Comput., 17, 1253-1262 (1988) · Zbl 0669.68049
[17]	Shiloach, Y.; Vishkin, U., Finding the maximum, merging and sorting in a parallel computation model, J. Algorithms, 2, 88-102 (1981) · Zbl 0456.68062
[18]	Shiloach, Y.; Vishkin, U., An \(O(n^2\) log \(n)\) parallel max-flow algorithm, J. Algorithms, 3, 128-146 (1982) · Zbl 0483.90044
[19]	Valiant, L. G., Parallelism in comparison models, SIAM J. Comput., 4, 348-355 (1975) · Zbl 0311.68033
[20]	Vishkin, U., Synchronous parallel computation — a survey, (Tech. Rept. TR # 71 (1983), Department of Computer Science, Courant Institute, New York University)
[21]	Yang, C. C.; Lee, D. T., A note on the All Nearest Neighbor problem for convex polygons, Inform. Process. Lett., 8, 193-194 (1979) · Zbl 0399.68071