zbMATH — the first resource for mathematics

\(O(\log \log n)\)-time integer geometry on the CRCW PRAM. (English) Zbl 0837.68121
Summary: We study problems in computational geometry on PRAMs under the assumption that input objects are specified by points with \(O (\log n)\)-bit coordinates, or, equivalently, with polynomially bounded integer coordinates. We show that in this setting many geometric problems can be solved in time \(O (\log \log n)\). The following five specific problems are investigated: closest pair of points, intersection of convex polygons, intersection of Manhattan line segments, dominating set, and largest empty square. Algorithms solving them are developed which operate in time \(O (\log \log n)\) on the arbitrary CRCW PRAM. The number of processors used is either \(O(n)\) or \(O(n \log n)\).
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI
[1] A. Aggarwal, B. Chazelle, L. Guibas, C. O’Dunlaing, and C. K. Yap, Parallel computational geometry,Algorithmica,3 (1988), 293-326. · Zbl 0664.68041 · doi:10.1007/BF01762120
[2] M. J. Atallah and M. Goodrich, Efficient parallel solutions to some geometric problems,J. Parallel Distributed Comput.,3 (1986), 492-507. · doi:10.1016/0743-7315(86)90011-0
[3] P. Beame and J. Hastad, Optimal bounds for decision problems on the CRCW PRAM,Proceedings of the 19th ACM Symposium on Theory of Computing, 1987, pp. 83-93.
[4] O. Berkman, D. Breslauer, Z. Galil, B. Schieber, and U. Vishkin, Highly-parallelizable problems,Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 309-319.
[5] O. Berkman, J. JáJá, S. Krishnamurthy, R. Thurimella, and U. Vishkin, Some triply-logarithmic parallel algorithms,Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1980, pp. 871-881.
[6] P. C. P. Bhatt, K. Diks, T, Hagerup, V. C. Prasad, T. Radzik, and S. Saxena, Improved deterministic parallel integer sorting,Inform. and Comput.,94 (1991), 29-47. · Zbl 0768.68023 · doi:10.1016/0890-5401(91)90031-V
[7] B. S. Chlebus, K. Diks, T. Hagerup, and T. Radzik, Efficient simulations between concurrent-read concurrent-write PRAM models,Proceedings of the 13th Symposium on Mathematical Foundations of Computer Science, 1988, Lecture Notes in Computer Science, Vol. 324, Springer-Verlag, Berlin, pp. 231-239.
[8] R. Cole and M. T. Goodrich, Optimal parallel algorithms for polygon and pointset problems,Proceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 205-214.
[9] T. Hagerup, The log-star revolution,Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, 1992, Lecture Notes in Computer Science, Vol. 577, Springer-Verlag, Berlin, pp. 259-278.
[10] P. D. MacKenzie and Q. F. Stout, Ultra-fast expected time parallel algorithms,Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1991, pp. 414-423. · Zbl 0800.68469
[11] Y. Shiloach and U. Vishkin, Finding the maximum, merging, and sorting in a parallel computation model,J. Algorithms,3 (1981), 57-67. · Zbl 0494.68070 · doi:10.1016/0196-6774(82)90008-6
[12] Q. F. Stout, Constant-time geometry on PRAMs,Proceedings of the International Conference on Parallel Processing, 1988, pp. 104-107.
[13] U. Vishkin, Structural parallel algorithmics, inLectures on Parallel Computation, edited by A. Gibbons and P. Spirakis, Cambridge University Press, Cambridge, 1993, pp. 1-18.
[14] H. Wagener, Optimal parallel hull construction for simple polygons in O(log logn) time,Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 593-599. · Zbl 0977.68569
[15] D. E. Willard and Y. C. Wee, Quasi-valid range querying and its implications for nearest neighbor problems,Proceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 34-43.
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.