×

Visibility graphs and obstacle-avoiding shortest paths. (English) Zbl 0656.05062

Two closely related problems in computational geometry are determining visibility graphs and shortest paths in a two- or three-dimensional environment containing obstacles. Applications are within computer graphics and robotics. We give a survey on recent research done on efficient algorithms for these problems.

MSC:

05C99 Graph theory
05C38 Paths and cycles
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley
[2] Asano T, Asano T, Guibas L, Hershberger J, Imai H (1986) Visibility of disjoint polygons. Algorithmica 1:49–63 · Zbl 0611.68062 · doi:10.1007/BF01840436
[3] Baker B (1985) Shortest paths with unit clearance among polygonal obstacles. SIAM Conference on Geometrical Modelling and Robotics
[4] Canny J (1987) A new algebraic method for robot motion planning and real geometry. In: Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pp 39–48
[5] Canny J, Reif J (1987) New lower bound techniques for robot motion planning problems. In: Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, pp 49–60
[6] Chew LP (1987) Planar graphs and sparse graphs for efficient motion planning in the plane. Manuscript
[7] Chew LP (1985) Planning the shortest path for a disk inO(n 2 logn) time. In: Proceedings of the 1st Annual Symposium on Computational Geometry, pp 214–220
[8] Clarkson K (1987) Approximation algorithms for shortest path motion planning. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp 56–65
[9] Clarkson K, Kapoor S, Vaidya P (1987) Rectilinear shortest paths through polygonal obstacles inO(n log 2 n) time. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, pp 251–257
[10] Collins GE (1975) Quantifier elimination for real closed fields by cylindric algebraic decomposition. In: Proceedings 2nd GI-Conference on Automata Theory and Formal Languages, Lecture Notes in Computer Science 35, Springer-Verlag, pp 134–183
[11] Edelsbrunner H (1987) Algorithms in combinatorial geometry. Springer-Verlag · Zbl 0634.52001
[12] Edelsbrunner H, Guibas L (1986) Topologically sweeping in an arrangement. In: Proceedings of the 18th ACM Symposium on Theory of Consumpting, pp 389–403 · Zbl 0676.68013
[13] Fredman M, Tarjan R (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J of the Association for Computing Machinery 34:596–615
[14] Ghosh SK, Mount DM (1987) An output sensitive algorithm for computing visibility graphs. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pp 11–19
[15] Guibas LJ, Hershberger J (1987) Optimal shortest path queries in a simple polygon. In: Proceedings of the 9rd Annual Symposium on Computational Geometry, pp 50–63
[16] Hershberger JE (1987) Efficient algorithms for shortest path and visibility problems. Dissertation, Stanford University
[17] Hershberger JE, Guibas LJ (1986) AnO(n 2 ) shortest path algorithm for a non-rotating convex body. Technical Report, DEC Systems Research Center
[18] Lee DT (1978) Proximity and reachability in the plane. Dissertation, University of Illinois at Urbana-Champaign
[19] Lee DT, Preparata FP (1984) Euclidean shortest paths in the presence of rectilinear barriers. Networks 14:393–410 · Zbl 0545.90098 · doi:10.1002/net.3230140304
[20] Lozano-Perez T, Wesley MA (1979) An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM 22:560–570 · doi:10.1145/359156.359164
[21] Masser M (1988) Algorithmen zur Konstruktion von Sichtbarkeitsgraphen. Diplomarbeit, Institutes for Information Processing, IIG, Technical University of Graz, in preparation
[22] Mehlhorn K (1984) Data structures and algorithms 2: graph algorithms and NP-completeness. Springer-Verlag · Zbl 0556.68002
[23] Mehlhorn K (1984) Data structures and algorithms 3: multidimensional searching and computational geometry. Springer-Verlag · Zbl 0556.68003
[24] Mitchell JSB, Papadimitriou CH (1987) The weighted region problem. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, pp 30–38
[25] Mitchel JSB, Mount DM, Papadimitriou CH (1987) The discrete geodesic problem. SIAM J Computing 23:647–668 · Zbl 0625.68051 · doi:10.1137/0216045
[26] Overmars M, Welzl E (1987) Construction of sparse visibility graphs. Report RUU-CS-87-9, Department of Computer Science, University of Utrecht
[27] Overmars M, Welzl E (1988) New methods for computing visibility graphs. To appear in: Proceedings of the 4th Annual Symposium on Computational Geometry
[28] Papadimitriou CH (1985) An algorithm for shortest path motion in three dimensions. Inform Process Lett 20:259–263 · Zbl 0603.68070 · doi:10.1016/0020-0190(85)90029-8
[29] Papadimitriou CH, Silverberg EB (1986) Optimal piecewise linear motion of an object among obstacles. Technical Report, Dept. of Operations Research, Stanford University
[30] Preparata FP, Shamos MI (1985) Computational geometry. Springer Verlag
[31] Reif J, Storer JA (1985) Shortest paths in Euclidean space with polyhedral obstacles. Technical Report CS-85-121, Computer Science Department, Brandeis University
[32] Rohner H (1986) Shortest paths in the plane with convex polygonal obstacles. Inform Process Lett 23:71–76 · Zbl 0607.68052 · doi:10.1016/0020-0190(86)90045-1
[33] Schorr A, Sharir M (1986) On shortest paths in polyhedral spaces. SIAM J Computing 15:193–215 · Zbl 0612.68090 · doi:10.1137/0215014
[34] Tarjan RE, van Wyk C (1986) AnO(n log log n)-time algorithm for triangulating simple polygons. Manuscript
[35] Welzl E (1985) Constructing the visibility graph forn line segments inO(n 2) time. Inform Process Lett 20:167–171 · Zbl 0573.68036 · doi:10.1016/0020-0190(85)90044-4
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.