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

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.


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
Full Text: DOI


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.