Selected topics from computational geometry, data structures and motion planning

1. Ta. Asano, Te. Asano, L.J. Guibas, J. Hershberger, and H. Imai. Visibility-polygon search and euclidean shortest paths. Algorithmica, 1(1):49–64, 1986.

   Google Scholar 

2. H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig. Approximate motion planning and the complexity of the boundary of the union of simple plane figures. In Proc. of the 6th ACM Symposium on Computational Geometry, pages 281–289, 1990.

   Google Scholar 

3. M.J. Atallah, M.G. Goodrich, and M.H. Overmars. New output-sensitive methods for rectilinear hidden surface removal. Presented on a Workshop on Computational Geometry in Princeton, Oct. 1989.

   Google Scholar 

4. A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, 1974.

   Google Scholar 

5. F. Aurenhammer. Voronoi diagrams — a survey of a fundamental geometric data structure. Technical Report B 90-09, Freie Universität Berlin, 1990. To appear in ACM Computing Surveys.

   Google Scholar 

6. H. Alt and E. Welzl. Visibility graphs and obstacle-avoiding shortest paths. Zeitschrift für Operations Research, 32:145–164, 1988.

   Google Scholar 

7. J. D. Boissonnat and M. Devillers-Teillaud. On the randomized construction of the delaunay tree. Technical Report 1140, INRIA Sophia-Antipolis, 1989.

   Google Scholar 

8. J. D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Technical Report 1285, INRIA Sophia-Antipolis, 1990.

   Google Scholar 

9. J. D. Boissonnat, O. Devillers, and M. Teillaud. A dynamic construction of higher order voronoi diagrams and its randomized analysis. Technical Report 1207, INRIA Sophia-Antipolis, 1990.

   Google Scholar 

10. J.L. Bentley. Solutions to klee's rectangle problems. Unpublished manuscript, Carnegie-Mellon University, Department of Computer Science, 1977.

    Google Scholar 

11. M. Bern. Hidden surface removal for rectangles. In Proc. of the 4th ACM Symposium on Computational Geometry, pages 183–192, 1988.

    Google Scholar 

12. M. Bern. Hidden surface removal for rectangles. Personal Communication, Oct. 1989.

    Google Scholar 

13. H. Baumgarten, H. Jung, and K. Mehlhorn. Dynamic point location in general subdivisions. To be presented at the ACM-SIAM Symposium on Discrete Algorithms, 1992.

    Google Scholar 

14. N. Blum. On the single-operation worst-case time complexity of the disjoint set union problem. SIAM Journal on Computing, 15(4):1021–1024, 1986.

    Article  Google Scholar 

15. K.Q. Brown. Voronoi diagrams from convex hulls. Information Processing Letters, 9:223–228, 1979.

    Article  Google Scholar 

16. B. Chazelle and L.J. Guibas. Fractional cascading. Algorithmica, 1:133–196, 1986.

    MathSciNet  Google Scholar 

17. L.P. Chew. Planning the shortest path for a disc in o(n ² log n) time. In Proc. of the 1st ACM Symposium on Computational Geometry, pages 214–220, 1985.

    Google Scholar 

18. S.W. Cheng and R. Janardan. New results on dynamic planar point location. In Proc. of the 31th Annual IEEE Symposium on Foundations of Computer Science, volume 1, pages 96–105, 1990.

    Article  Google Scholar 

19. L.P. Chew and K. Kedem. High-clearance motion planning for a convex polygon among polygonal obstacles. Technical Report 184/90, Tel Aviv University, 1990.

    Google Scholar 

20. K.L. Clarkson and P.W. Shor. Applications of random sampling in computational geometry, ii. Discrete and Computational Geometry, 4:387–421, 1989.

    Google Scholar 

21. Y.J. Ching and R. Tamassia. Dynamization of the trapezoid method for planar point location. Proc. of the 7th ACM Symposium on Computational Geometry, 1991.

    Google Scholar 

22. D. Dobkin and L. Snyder. On a general method for maximizing and minimizing among certain geometric problems. In Proc. of the 20th Annual IEEE Symposium on Foundations of Computer Science, pages 9–17, 1979.

    Google Scholar 

23. H. Edelsbrunner, L.J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal on Computing, 15(2):317–340, 1986.

    Article  Google Scholar 

24. P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Systems Theory, 10:99–127, 1977.

    Article  Google Scholar 

25. H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Discrete and Computational Geometry, 1:25–44, 1986.

    Google Scholar 

26. R. Fleischer, K. Mehlhorn, G. Rote, E. Welzl, and C. Yap. On simultaneous inner and outer approximation of shapes. In Proc. of the 6th ACM Symposium on Computational Geometry, pages 216–224, 1990. Also available as ”Technical Report B 91-08, FU Berlin”.

    Google Scholar 

27. S. Fortune. A sweepline algorithm for voronoi diagrams. Algorithmica, 2:153–174, 1987.

    Article  Google Scholar 

28. O. Fries. Suche in dynamischen planaren Unterteilungen der Ebene. PhD thesis, Universität des Saarlandes, 1989.

    Google Scholar 

29. U. Fuchs, G. Rote, O. Schwarzkopf, and E. Welzl. Approximation of convex figures by pairs of rectangles. In Proc. of the 7th Annual Symposium on Theoretical Aspects of Computer Science, pages 240–249, 1990.

    Google Scholar 

30. L.J. Guibas, D.E. Knuth, and M. Sharir. Randomized incremental construction of delaunay and voronoi diagrams. In Proc. of the 17th International Colloqium on Automata, Languages and Programming, pages 414–431, Warwick, 1990. LNCS 443.

    Google Scholar 

31. S.K. Ghosh and D.M. Mount. An output sensitive algorithm for computing visibility graphs. Technical Report CS-TR-1874, University of Maryland, 1987.

    Google Scholar 

32. R.H. Güting and T.H. Ottmann. New algorithms for special cases of the hidden line elimination problem. Computer Vision, Graphics and Image Processing, 40, 1987.

    Google Scholar 

33. P.M. Gruber. Approximation of convex bodies. In Convexity and its Applications, pages 131–162. Birkhäuser Verlag, 1983.

    Google Scholar 

34. M.T. Goodrich and R. Tamassia. Dynamic trees and dynamic point location. In Proc. of the ACM Symposium on Theory of Computing, 1991.

    Google Scholar 

35. D. Halperin and M. Overmars. Efficient motion planning for an l-shaped object. In Proc. of the 5th ACM Symposium on Computational Geometry, pages 156–166, 1989.

    Google Scholar 

36. R. Klein. Abstract voronoi diagrams and their applications (extended abstract). In H. Noltemeier, editor, Proc. of the Workshop on Computational Geometry and its Applications, pages 148–157, Würzburg, 1988. LNCS 333.

    Google Scholar 

37. R. Klein. Voronoi diagrams in the moscow metric (extended abstract). In J. van Leeuwen, editor, Proc. of the Workshop on Graphtheoretic Concepts in Computer Science, pages 434–441, Amsterdam, 1988. LNCS 344.

    Google Scholar 

38. R. Klein. Combinatorial properties of abstract voronoi diagrams. In M. Nagl, editor, Proc. of the Workshop on Graphtheoretic Concepts in Computer Science, pages 356–369, Rolduc, 1989. LNCS 411.

    Google Scholar 

39. R. Klein. Concrete and Abstract Voronoi Diagrams. Springer Verlag, 1989. LNCS 400.

    Google Scholar 

40. K. Kedem, R. Livne, J. Pach, and M. Sharir. On the union of jordan regions and collision-free motion amidst polygonal obstacles. Discrete and Computational Geometry, 1:59–71, 1986.

    Google Scholar 

41. R. Kannan, L. Lovász, and H.E. Scarf. The shapes of polyhedra. Mathematics of Operations Research, 15:364–380, 1990.

    Google Scholar 

42. S. Kapoor and S.N. Maheshwari. Efficient algorithms for euclidean shortest path and visibility problems with polygonal obstacles. In Proc. of the 4th ACM Symposium on Computational Geometry, pages 172–182, 1988.

    Google Scholar 

43. R. Klein, K. Mehlhorn, and St. Meiser. Randomized incremental construction of abstract voronoi diagrams. Unpublished manuscript, 1991.

    Google Scholar 

44. A.N. Kolmogorov. On the notion of algorithm. Uspehi Mat. Nauk., 8:175–176, 1953.

    Google Scholar 

45. K. Kedem and M. Sharir. An automatic motion planning system for a convex polygonal mobile robot in 2-d polygonal space. In Proc. of the 4th ACM Symposium on Computational Geometry, pages 329–340, 1988.

    Google Scholar 

46. D.T. Lee and F.P. Preparata. Location of a point in a planar subdivision and its applications. SIAM Journal on Computing, 6(3):594–606, 1977.

    Article  Google Scholar 

47. D.T. Lee and F.P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14:393–410, 1984.

    Google Scholar 

48. R. Livne and M. Sharir. On intersection of planar jordan curves. Technical Report TR 153, N.Y. University, Courant Institute, 1985.

    Google Scholar 

49. D. Leven and M. Sharir. Intersection and proximity problems and voronoi diagrams. In J. Schwartz and C.K. Yap, editors, Advances in Robotics, Volume 1, pages 187–228. Lawrence Erlbaum, 1986.

    Google Scholar 

50. K. Mehlhorn. Data Structures and Algorithms. Springer Verlag, 1984.

    Google Scholar 

51. K. Mehlhorn, St. Meiser, and C. ó'DÚnlaing. On the construction of abstract voronoi diagrams. Discrete and Computational Geometry, 6:211–224, 1991.

    Google Scholar 

52. K. Mehlhorn and S. Näher. Dynamic fractional cascading. Algorithmica, 5:215–241, 1990.

    Google Scholar 

53. K. Mehlhorn, St. Näher, and H. Alt. A lower bound on the complexity of the union-split-find problem. SIAM Journal on Computing, 17(6):1093–1102, 1988.

    Google Scholar 

54. K. Mehlhorn, S. Näher, and C. Uhrig. Hidden line elimination for isooriented rectangles. Information Processing Letters, 35:137–143, 1990.

    Google Scholar 

55. M.H. Overmars. Range searching in a set of line segments. In Proc. of the 1st ACM Symposium on Computational Geometry, pages 177–185, 1985.

    Google Scholar 

56. T. Ottmann and D. Wood. The contour problem for polygons. Technical Report CS-84-33, University of Waterloo, 1984.

    Google Scholar 

57. M.H. Overmars and E. Welzl. New methods for computing visibility graphs. In Proc. of the 4th ACM Symposium on Computational Geometry, pages 164–171, 1988.

    Google Scholar 

58. C. ó'DÚnlaing and C.K. Yap. A ‘retraction’ method for planning the motion of a disc. Journal of Algorithms, 6:104–111, 1985.

    Google Scholar 

59. F.P. Preparata and R. Tamassia. Fully dynamic techniques fo point location and transitive closure in planar structures (ea). In Proc. of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 558–567, 1988.

    Google Scholar 

60. F.P. Preparata and R. Tamassia. Fully dynamic point location in a monotone subdivision. SIAM Journal on Computing, 18:811–830, 1989.

    Google Scholar 

61. F. P. Preparata, J. S. Vitter, and M. Yvinec. Computation of the axial view of a set of isothetic parallelepipeds. Technical Report LIENS-88-1, Laboratoire d'Informatique, Ecole Normale Superieure, Paris, 1988.

    Google Scholar 

62. H. Rohnert. Shortest paths in the plane with convex polygonal obstacles. Information Processing Letters, 23:71–76, 1986.

    Google Scholar 

63. H. Rohnert. Time and space efficient algorithms for shortest paths between convex polygons. Information Processing Letters, 27:175–179, 1988.

    MathSciNet  Google Scholar 

64. H. Rohnert. Bewegungsplanung in der Ebene. PhD thesis, Universität des Saarlandes, 1989.

    Google Scholar 

65. H. Rohnert. Moving a disk between polygons. Algorithmica, 6(2):182–191, 1991.

    Google Scholar 

66. S. Schirra. Approximative Bewegungsplanungsverfahren. PhD thesis, Universität des Saarlandes. In preparation.

    Google Scholar 

67. A. Schönhage. Storage modification machines. SIAM Journal on Computing, 9:490–508, 1980.

    Google Scholar 

68. M.I. Shamos and D. Hoey. Closest point problems. In Proc. of the 16th Annual IEEE Symposium on Foundations of Computer Science, pages 151–162, 1975.

    Google Scholar 

69. J.T. Schwartz and M. Sharir. Algorithmic motion planning in robotics. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. Elsevier, 1990.

    Google Scholar 

70. R.E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. Journal of Computer and System Sciences, 18:110–127, 1979.

    Google Scholar 

71. E. Welzl. Constructing the visibility graph for n line segments in o(n ²) time. Information Processing Letters, 20:167–171, 1985.

    Google Scholar 

Download references