Applications of a new space-partitioning technique

1. P. K. Agarwal, Ray shooting and other applications of spanning trees with low stabbing number,SIAM J. Comput. 21 (1992), in press.

2. P. K. Agarwal, Partitioning arrangements of lines, I: An efficient deterministic algorithm,Discrete Comput. Geom. 5 (1990), 449–483.

   Article  MathSciNet  MATH  Google Scholar 

3. P. K. Agarwal, Partitioning arrangements of lines, II: Applications,Discrete Comput. Geom. 5 (1990), 533–573.

   Article  MathSciNet  MATH  Google Scholar 

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.

6. P. K. Agarwal and J. Matoušek, Range searching with non-linear objects, in preparation, 1991.

7. B. Aronov and M. Sharir, On the zone of a surface in a hyperplane arrangement,Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 519, Springer-Verlag, Berlin, 1991, pp. 13–19.

   Chapter  Google Scholar 

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.

   Article  MathSciNet  Google Scholar 

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.

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.

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.

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.

15. B. Chazelle and L. Guibas, Visibility and intersection problems in plane geometry,Discrete Comput. Geom. 4 (1989), 551–589.

    Article  MathSciNet  MATH  Google Scholar 

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.

17. B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces of finite Vapnik-Chervonenkis dimensions,Discrete Comput. Geom. 4 (1989), 467–489.

    Article  MathSciNet  Google Scholar 

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.

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.

    Article  MathSciNet  MATH  Google Scholar 

21. R. Cole and M. Sharir, Visibility problems for polyhedral terrains,J. Symbolic Comput. 7 (1989), 11–30.

    Article  MathSciNet  Google Scholar 

22. D. Dobkin and H. Edelsbrunner, Space searching for intersecting objects,J. Algorithms 8 (1987), 348–361.

    Article  MathSciNet  Google Scholar 

23. D. Dobkin and D. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra,J. Algorithms 6 (1985), 381–392.

    Article  MathSciNet  MATH  Google Scholar 

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.

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.

    Article  MathSciNet  MATH  Google Scholar 

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.

    MATH  Google Scholar 

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.

32. K. Mehlhorn,Data Structures and Algorithms, 3: Multi-Dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984.

    Book  MATH  Google Scholar 

33. M. Overmars and J. van Leeuwen, Maintenance of configurations in the plane,J. Comput. System Sci. 23 (1981), 166–204.

    Article  MathSciNet  MATH  Google Scholar 

34. M. Overmars and J. van Leeuwen, Worst-case optimal insertion and deletion methods for decomposable searching,Inform. Process. Lett. 12 (1981), 168–173.

    Article  MATH  Google Scholar 

35. M. Overmars, H. Schipper, and M. Sharir, Storing line segments in partition trees,BIT 30 (1990), 385–403.

    Article  MathSciNet  MATH  Google Scholar 

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.)

38. M. Overmars and M. Sharir, Merging visibility maps,Comput. Geom. Theory Applic. 1 (1991), 35–50.

    Article  MathSciNet  MATH  Google Scholar 

39. M. Pellegrini, Combinatorial and algorithmic analysis of stabbing and visibility problems in 3-dimensional space, Ph.D. Thesis, New York University, 1991.

40. A. Schmitt, H. Müller, and W. Leister, Ray tracing algorithms—theory and algorithms, inTheoretical Foundations of Computer Graphics and CAD (ed. R. Earnshaw), NATO Series, Springer-Verlag, Berlin, 1988, pp. 997–1030.

    Chapter  Google Scholar 

41. M. Sharir and M. Overmars, A simple output-sensitive hidden surface removal algorithm,ACM Trans. Graphics 11 (1992), 1–11.

    Article  MathSciNet  MATH  Google Scholar 

42. D. M. H. Sommerville,Analytical Geometry in Three Dimensions, Cambridge University Press, Cambridge, 1951.

    Google Scholar 

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.

Download references