×

Constructing arrangements optimally in parallel. (English) Zbl 0788.68142

Summary: We give two optimal parallel algorithms for constructing the arrangement of \(n\) lines in the plane. The first method is quite simple and runs in \(O(\log^ 2n)\) time using \(O(n^ 2)\) work, and the second method, which is more sophisticated, runs in \(O(\log n)\) times using \(O(n^ 2)\) work. This second result solves a well-known open problem in parallel computational geometry, and involves the use of a new algorithmic technique, the construction of an \(\varepsilon\)-pseudocutting. Our results immediately imply that the arrangement of \(n\) hyperplanes in \(\mathbb{R}^ d\) in \(O(\log n)\) time using \(O(n^ d)\) work, for fixed \(d\), can be optimally constructed. Our algorithms are for the CREW PRAM.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] P. K. Agarwal, Partitioning Arrangements of Lines, II: Applications,Discrete Comput. Geom.5 (1990), 533-573. · Zbl 0709.68108 · doi:10.1007/BF02187809
[2] P. K. Agarwal, Geometric Partitioning and Its Applications, Technical Report CS-1991-27, Dept. of Computer Science, Duke University, 1991. · Zbl 0733.68081
[3] A. Aggarwal, B. Chazelle, L. Guibas, C. Ó’Dúnlaing, and C. Yap, Parallel Computational Geometry,Algorithmica3 (1988), 293-328. · Zbl 0664.68041 · doi:10.1007/BF01762120
[4] A. Aggarwal and J. Wein,Computational Geometry, M.I.T. Report MIT/LCS/RSS 3, 1988.
[5] R. Anderson, P. Beame, and E. Brisson, Parallel Algorithms for Arrangements,Proc. 2nd ACM Symp. on Parallel Algorithms and Architectures, 1990, pp. 298-306. (An expanded version of this paper is available as Technical Report 89-12-08, Dept. of Computer Science and Engineering, University of Washington, 1989.) · Zbl 0836.68050
[6] Anderson, R. J.; Miller, G. L., Deterministic Parallel List Ranking, No. 319, 81-90 (1988), Berlin · Zbl 0652.68037
[7] M. J. Atallah, R. Cole, and M. T. Goodrich, Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms,SIAM J. Comput.18 (1989), 499-532. · Zbl 0677.68022 · doi:10.1137/0218035
[8] J. L. Bentley and T. Ottmann, Algorithms for Reporting and Counting Geometric Intersections,IEEE Trans. Comput.28 (1979), 643-647. · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[9] L. J. Bentley and D. Wood, An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles,IEEE Trans. Comput.29 (1980), 571-576. · doi:10.1109/TC.1980.1675628
[10] G. Bilardi and A. Nicolau, Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared Memory Machines, Technical Report 86-769, Dept. of Computer Science, Cornell University, August 1986. · Zbl 0677.68070
[11] A. Borodin and J. E. Hopcroft, Routing, Merging, and Sorting on Parallel Models of Computation,J. Comput. System Sci.30 (1985), 130-145. · Zbl 0603.68065 · doi:10.1016/0022-0000(85)90008-X
[12] R. P. Brent, The Parallel Evaluation of General Arithmetic Expressions,J. Assoc. Comput. Mach.21 (1974), 201-206. · Zbl 0276.68010 · doi:10.1145/321812.321815
[13] B. Chazelle, Reporting and Counting Segment Intersections,J. Comput. System Sci.32 (1986), 156-182. · Zbl 0616.68042 · doi:10.1016/0022-0000(86)90025-5
[14] B. Chazelle, An Optimal Convex Hull Algorithm and New Results on Cuttings,Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 29-38.
[15] B. Chazelle and H. Edelsbrunner, An Optimal Algorithm for Intersecting Line Segments in the Plane,J. Assoc. Comput. Mach.39 (1992), 1-54. · Zbl 0799.68191 · doi:10.1145/147508.147511
[16] B. Chazelle, L. J. Guibas, and D. T. Lee, The Power of Geometric Duality,BIT25 (1985), 76-90. · Zbl 0603.68072 · doi:10.1007/BF01934990
[17] A. Chow, Parallel Algorithms for Geometric Problems, Ph.D. thesis, Computer Science Dept., University of Illinois, 1980.
[18] K. L. Clarkson, New Applications of Random Sampling in Computational Geometry,Discrete Comput. Geom.2 (1987), 195-222. · Zbl 0615.68037 · doi:10.1007/BF02187879
[19] K. L. Clarkson, R. Cole, and R. E. Tarjan, Randomized Parallel Algorithms for Trapezoidal Diagrams,Internat. J. Comput. Geom. Appl.2 (1992), 117-134. · Zbl 0762.68062 · doi:10.1142/S0218195992000081
[20] R. Cole, Parallel Merge Sort,SIAM J. Comput.17 (1988), 770-785. · Zbl 0651.68077 · doi:10.1137/0217049
[21] R. Cole and U. Vishkin, Deterministic Coin Tossing and Accelerating Cascades: Micro and Macro Techniques for Designing Parallel Algorithms,Proc. 18th ACM Symp. on Theory of Computing, 1986, pp. 206-219.
[22] R. Cole and U. Vishkin, Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems,Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 478-491.
[23] F. Dévai, Quadratic Bounds for Hidden-Line Elimination,Proc. 2nd ACM Symp. on Computational Geometry, 1986, pp. 269-275.
[24] P. W. Dymon and S. A. Cook, Hardware Complexity and Parallel Computation,Proc. 21st IEEE Symp. on Foundations of Computer Science, 1980, pp. 360-372.
[25] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[26] H. Edelsbrunner and L. J. Guibas, Topologically Sweeping an Arrangement,J. Comput. System Sci.38 (1989), 165-194. · Zbl 0676.68013 · doi:10.1016/0022-0000(89)90038-X
[27] H. Edelsbrunner, J. O’Rourke, and R. Seidel, Constructing Arrangements of Lines and Hyperplanes with Applications,SIAM J. Comput.15 (1986), 341-363. · Zbl 0603.68104 · doi:10.1137/0215024
[28] M. T. Goodrich, Efficient Parallel Techniques for Computational Geometry, Ph.D. thesis, Dept. Computer Sciences, Purdue University, 1987.
[29] M. T. Goodrich, Intersecting Line Segments in Parallel with an Output-Sensitive Number of Processors,SIAM J. Comput.20 (1991), 737-755. · Zbl 0736.68034 · doi:10.1137/0220047
[30] M. T. Goodrich and S. R. Kosaraju, Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 190-195.
[31] T. Hagerup, H. Jung, and E. Welzl, Efficient Parallel Computation of Arrangement of Hyperplanes ind Dimensions,Proc. 2nd ACM Symp. on Parallel Algorithms and Architectures, 1990, pp. 290-297.
[32] D. Haussler and E. Welzl, ɛ-Nets and Simplex Range Queries,Discrete Comput. Geom.2 (1987), 127-151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[33] J. JáJá,An Introduction to Parallel Algorithms, Addison-Wesley, Reading, MA, 1992. · Zbl 0781.68009
[34] Karp, R. M.; Ramachandran, V.; Leeuwen, J. (ed.), Parallel Algorithms for Shared-Memory Machines, 869-942 (1990), Cambridge, MA · Zbl 0900.68267
[35] C. P. Kruskal, Searching, Merging, and Sorting in Parallel Computation,IEEE Trans. Comput.32 (1983), 942-946. · Zbl 0525.68039 · doi:10.1109/TC.1983.1676138
[36] C. P. Kruskal, L. Rudolph, and M. Snir, The Power of Parallel Prefix,Proc. 1985 Internat. Conf. on Parallel Processing, 1985, pp. 180-185.
[37] R. E. Ladner and M. J. Fischer, Parallel Prefix Computation,J. Assoc. Comput. Mach.27 (1980), 831-838. · Zbl 0445.68066 · doi:10.1145/322217.322232
[38] D. T. Lee and F. P. Preparata, Computational Geometry—A Survey,IEEE Trans. Comput.33 (1984), 872-1101.
[39] J. Matoušek, Approximations and Optimal Geometric Divide-and-Conquer,Proc. 23rd ACM Symp. on Theory of Computing, 1991, pp. 505-511.
[40] F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. · Zbl 0759.68037 · doi:10.1007/978-1-4612-1098-6
[41] C. Rüb, Line Segment Intersection Reporting in Parallel,Algorithmica8 (1992), 119-144. · Zbl 0753.68095 · doi:10.1007/BF01758839
[42] W. L. Ruzzo, On Uniform Circuit Complexity,J. Comput. System Sci.22 (1981), 365-383. · Zbl 0462.68013 · doi:10.1016/0022-0000(81)90038-6
[43] Y. Shiloach and U. Vishkin, Finding the Maximum, Merging, and Sorting in a Parallel Computation Model,J. Algorithms2 (1981), 88-102. · Zbl 0456.68062 · doi:10.1016/0196-6774(81)90010-9
[44] J. C. Wyllie, The Complexity of Parallel Computation, Ph.D. thesis, Technical Report 79-387, Dept. of Computer Science, Cornell University, 1979.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.