×

Applications of a new space-partitioning technique. (English) Zbl 0773.68065

Summary: We present several applications of a recent space-partitioning technique of B. Chazelle, M. Sharir and E. Welzl [Quasi-optimal upper bounds for simplex range searching and new zone theorems, Proc. 6th ACM Symp. on Computational Geometry, 23-33 (1990)]. Our results include efficient algorithms for output-sensitive hidden surface removal, for ray shooting in two and three dimensions, and for constructing spanning trees with low stabbing number.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number,SIAM J. Comput.21 (1992), in press. · Zbl 0756.68091
[2] P. K. Agarwal, Partitioning arrangements of lines, I: An efficient deterministic algorithm,Discrete Comput. Geom.5 (1990), 449-483. · Zbl 1092.83502 · doi:10.1007/BF02187805
[3] P. K. Agarwal, Partitioning arrangements of lines, II: Applications,Discrete Comput. Geom.5 (1990), 533-573. · Zbl 0709.68108 · doi:10.1007/BF02187809
[4] P. K. Agarwal, M. van Kreveld, and M. Overmars, Searching and storing curved objects,Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 41-50. (Also to appear inJ. Algorithms.)
[5] P. K. Agarwal and J. Matoušek, Ray shooting and parametric search,Proc. 24th ACM Symp. on Theory of Computing, 1992. · Zbl 0777.68042
[6] P. K. Agarwal and J. Matoušek, Range searching with non-linear objects, in preparation, 1991.
[7] Aronov, B.; Sharir, M., On the zone of a surface in a hyperplane arrangement, No. 519, 13-19 (1991), Berlin · Zbl 0764.68166 · doi:10.1007/BFb0028245
[8] R. Bar Yehuda and S. Fogel, Good splitters with applications to ray shooting,Proc. 2nd Canadian Conf. on Computational Geometry, 1990, pp. 81-85. (Also to appear inAlgorithmica.)
[9] J. Bentley and J. Saxe, Decomposable searching problems, I: Static-to-dynamic transformation,J. Algorithms,1 (1980), 301-358. · Zbl 0461.68065 · doi:10.1016/0196-6774(80)90015-2
[10] M. de Berg, D. Halperin, M. Overmars, J. Snoeyink, and M. van Kreveld, Efficient ray shooting and hidden surface removal,Proc. 7th Symp. on Computational Geometry, 1991, pp. 21-30. · Zbl 0813.68160
[11] B. Chazelle, An optimal computing convex hull algorithm and new results on cuttings,Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 29-38.
[12] B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink Ray shooting in polygons using geodesic triangulations,Proc. 18th International Colloquium on Automata, Languages, and Programming, 1991, pp. 661-673. · Zbl 0769.68119
[13] B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, A singly-exponential stratification scheme for real semi-algebraic varieties and its applications,Proc. 16th International Colloquium on Automata, Languages and Programming, 1989, pp. 179-192. · Zbl 0702.68064
[14] B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Stolfi, Lines in space: Combinatorics and algorithms, Technical Report 491, Dept. of Computer Science, New York University, February 1990. · Zbl 0846.68098
[15] B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Discrete Comput. Geom.4 (1989), 551-589. · Zbl 0695.68033 · doi:10.1007/BF02187747
[16] B. Chazelle, M. Sharir, and E. Welzl, Quasi-optimal upper bounds for simplex range searching and new zone theorems,Proc. 6th ACM Symp. on Computational Geometry, 1990, pp. 23-33. · Zbl 0788.68141
[17] B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces of finite Vapnik-Chervonenkis dimensions,Discrete Comput. Geom.4 (1989), 467-489. · Zbl 0681.68081 · doi:10.1007/BF02187743
[18] S. W. Cheng and R. Janardan, New results on dynamic planar point location,Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 96-105.
[19] S. W. Cheng and R. Janardan, Space efficient ray shooting and intersection searching: Algorithms, dynamization, and applications,Proc. 2nd SIAM-ACM Symp. on Discrete Algorithms, 1991, pp. 7-16. · Zbl 0800.68362
[20] K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and spheres,Discrete Comput. Geom.5 (1990), 99-160. · Zbl 0704.51003 · doi:10.1007/BF02187783
[21] R. Cole and M. Sharir, Visibility problems for polyhedral terrains,J. Symbolic Comput.7 (1989), 11-30. · doi:10.1016/S0747-7171(89)80003-3
[22] D. Dobkin and H. Edelsbrunner, Space searching for intersecting objects,J. Algorithms8 (1987), 348-361. · Zbl 0643.68051 · doi:10.1016/0196-6774(87)90015-0
[23] D. Dobkin and D. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra,J. Algorithms6 (1985), 381-392. · Zbl 0577.52004 · doi:10.1016/0196-6774(85)90007-0
[24] D. Dobkin and D. Kirkpatrick, Determining the separation of preprocessed polyhedra: a unified approach,Proc. 17th International Colloquium on Automata, Languages, and Programming, 1990, pp. 400-413. · Zbl 0765.68205
[25] H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl, Implicitly representing arrangements of lines and of segments,Discrete Comput. Geom.4 (1989), 433-466. · Zbl 0688.68031 · doi:10.1007/BF02187742
[26] L. Guibas, M. Overmars, and M. Sharir, Ray shooting, implicit point location, and related queries in arrangements of segments, Technical Report 433, Courant Institute, New York University, 1989.
[27] J. Matoušek, More on cutting hyperplanes and spanning trees with low crossing number, Technical Report B-90-2, Freie Universität Berlin, 1990.
[28] J. Matoušek, Spanning trees with low crossing numbers,Inform. Théoret. Applic.25 (1991), 103-123. · Zbl 1198.74070
[29] J. Matoušek, Approximations and optimal geometric divide-and-conquer,Proc. 23rd ACM Symp. on Theory of Computing, 1991, 506-511.
[30] J. Matoušek, Efficient partition trees,Proc. 7th ACM Symp. on Computational Geometry, 1991, pp. 1-9.
[31] J. Matoušek, Range searching with efficient hierarchical cuttings,Proc. 8th ACM Symp. on Computational Geometry, 1992, to appear. · Zbl 0774.68101
[32] K. Mehlhorn,Data Structures and Algorithms, 3: Multi-Dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984. · Zbl 0556.68003 · doi:10.1007/978-3-642-69900-9
[33] M. Overmars and J. van Leeuwen, Maintenance of configurations in the plane,J. Comput. System Sci.23 (1981), 166-204. · Zbl 1309.60001 · doi:10.1016/0022-0000(81)90012-X
[34] M. Overmars and J. van Leeuwen, Worst-case optimal insertion and deletion methods for decomposable searching,Inform. Process. Lett.12 (1981), 168-173. · Zbl 0459.68026 · doi:10.1016/0020-0190(81)90093-4
[35] M. Overmars, H. Schipper, and M. Sharir, Storing line segments in partition trees,BIT30 (1990), 385-403. · Zbl 1217.74039 · doi:10.1007/BF01931656
[36] M. Overmars and M. Sharir, Output-sensitive hidden surface removal,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 598-603.
[37] M. Overmars and M. Sharir, An improved technique for output-sensitive hidden surface removal, Technical Report RUU-CS-89-32, Computer Science Department, University of Utrecht, December 1989. (To appear inAlgorithmica.) · Zbl 0804.68146
[38] M. Overmars and M. Sharir, Merging visibility maps,Comput. Geom. Theory Applic.1 (1991), 35-50. · Zbl 0731.68097 · doi:10.1016/0925-7721(91)90011-3
[39] M. Pellegrini, Combinatorial and algorithmic analysis of stabbing and visibility problems in 3-dimensional space, Ph.D. Thesis, New York University, 1991.
[40] Schmitt, A.; Müller, H.; Leister, W.; Earnshaw, R. (ed.), Ray tracing algorithms—theory and algorithms, 997-1030 (1988), Berlin · doi:10.1007/978-3-642-83539-1_42
[41] M. Sharir and M. Overmars, A simple output-sensitive hidden surface removal algorithm,ACM Trans. Graphics11 (1992), 1-11. · Zbl 0732.68100 · doi:10.1145/102377.112141
[42] D. M. H. Sommerville,Analytical Geometry in Three Dimensions, Cambridge University Press, Cambridge, 1951.
[43] J. Stolfi, Primitives for computational geometry, Ph.D. Thesis, Stanford University, 1989.
[44] E. Welzl, Partition trees for triangle counting and other range searching problems,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 23-33.
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.