×

Partitioning arrangements of lines. I: An efficient deterministic algorithm. (English) Zbl 0701.68035

Summary: We consider the following problem: Given a set \({\mathcal L}\) of n lines in the plane, partition the plane into \(0(r^ 2)\) triangles so that no triangle meets more than 0(n/r) lines of \({\mathcal L}\). We present a deterministic algorithm for this problem with 0(nr log n log\({}^{\omega}r)\) running time, where \(\omega\) is a constant \(<3.33\).

MSC:

68W10 Parallel algorithms in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] P. K. Agarwal, Partitioning arrangements of lines, II: Applications,Discrete and Computational Geometry5 (1990), 533-574. · Zbl 0709.68108 · doi:10.1007/BF02187809
[2] P. K. Agarwal and M. Sharir, Red-blue intersection detection algorithms with applications to motion planning and collision detection,SIAM Journal on Computing19 (1990), 297-322. · Zbl 0696.68044 · doi:10.1137/0219020
[3] M. Ajtai, J. Komlos, and E. Szemerédi, Sorting inc logn parallel steps,Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 1-9. · Zbl 0523.68048
[4] K. E. Batcher, Sorting networks and their applications,Proceedings of the AFIPS Spring Joint Summer Computer Conference, vol. 32 (1968), pp. 307-314.
[5] B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry,Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 539-549.
[6] K. Clarkson, A probabilistic algorithm for the post office problem,Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 75-84.
[7] K. Clarkson, New applications of random sampling in computational geometry,Discrete and Computational Geometry2 (1987), 195-222. · Zbl 0615.68037 · doi:10.1007/BF02187879
[8] K. Clarkson, Applications of random sampling in computational geometry, II,Proceedings of the 4th Annual Symposium on Computational Geometry, 1988, pp. 1-11.
[9] K. Clarkson and P. Shor, Algorithms for diametric pairs and convex hulls that are optimal, randomized and incremental,Proceedings of the 4th Annual Symposium on Computational Geometry, 1988, pp. 12-17.
[10] K. Clarkson, R. E. Tarjan, and C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon,Discrete and Computational Geometry4 (1989), 423-432. · Zbl 0681.68061 · doi:10.1007/BF02187741
[11] R. Cole, Slowing down sorting networks to obtain faster sorting algorithms,Journal of the Association for Computing Machinery31 (1984), 200-208. · Zbl 1378.68037
[12] R. Cole, J. Salowe, W. Steiger, and E. Szemerédi, An optimal-time algorithm for slope selection,SIAM Journal on Computing16 (1989), 792-810. · Zbl 0678.68033 · doi:10.1137/0218055
[13] R. Cole, M. Sharir, and C. K. Yap, Onk-hulls and related problems,SIAM Journal on Computing16 (1987), 61-77. · Zbl 0637.68074 · doi:10.1137/0216005
[14] H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987. · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9
[15] H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl, Implicitly representing arrangements of lines or segments,Discrete and Computational Geometry4 (1989), 433-466. · Zbl 0688.68031 · doi:10.1007/BF02187742
[16] H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity and construction of many faces in arrangements of lines or of segments,Discrete and Computational Geometry5 (1990), 161-196. · Zbl 0691.68035 · doi:10.1007/BF02187784
[17] H. Edelsbrunner and E. Welzl, Constructing belts in two-dimensional arrangements with applications,SIAM Journal on Computing15 (1986), 271-284. · Zbl 0613.68043 · doi:10.1137/0215019
[18] L. Guibas, M. Overmars, and M. Sharir, Ray shooting, implicit point location, and related queries in arrangements of segments, Technical Report 433, Dept. Computer Science, New York University, March 1989.
[19] D. Haussler and E. Welzl,ɛ-nets and simplex range queries,Discrete and Computational Geometry2 (1987), 127-151. · Zbl 0619.68056 · doi:10.1007/BF02187876
[20] J. Matoušek, Construction ofɛ-nets,Discrete and Computational Geometry, this issue, 427-448. · Zbl 0701.68040
[21] N. Megiddo, Applying parallel computation algorithms in design of serial algorithms,Journal of the Association of Computing Machinery30 (1983), 852-865. · Zbl 0627.68034 · doi:10.1145/2157.322410
[22] J. Reif and S. Sen, Optimal randomized parallel algorithms for computational geometry,Proceedings of the 16th International Conference on Parallel Processing, 1987, pp. 270-277.
[23] J. Reif and S. Sen, Polling: A new randomized sampling technique for computational geometry,Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 394-404.
[24] S. Suri, A linear algorithm for minimum link paths inside a simple polygon,Computer Vision, Graphics and Image Processing35 (1986), 99-110. · Zbl 0624.68101 · doi:10.1016/0734-189X(86)90127-1
[25] E. Welzl, More onk-sets of finite sets in the plane,Discrete and Computational Geometry1 (1986), 83-94. · Zbl 0598.52007 · doi:10.1007/BF02187686
[26] G. Woeginger, Epsilon-nets for half planes, Technical Report B-88-02, Dept. of Mathematics, Free University, Berlin, March 1988.
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.