{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:06:33Z","timestamp":1764936393799},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1988,5,1]],"date-time":"1988-05-01T00:00:00Z","timestamp":578448000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Zeitschrift f\u00fcr Operations Research"],"published-print":{"date-parts":[[1988,5]]},"DOI":"10.1007\/bf01928918","type":"journal-article","created":{"date-parts":[[2005,7,24]],"date-time":"2005-07-24T14:04:47Z","timestamp":1122213887000},"page":"145-164","source":"Crossref","is-referenced-by-count":20,"title":["Visibility graphs and obstacle-avoiding shortest paths"],"prefix":"10.1007","volume":"32","author":[{"given":"H.","family":"Alt","sequence":"first","affiliation":[]},{"given":"E.","family":"Welzl","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01928918_CR1","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley"},{"key":"BF01928918_CR2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF01840436","volume":"1","author":"T Asano","year":"1986","unstructured":"Asano T, Asano T, Guibas L, Hershberger J, Imai H (1986) Visibility of disjoint polygons. Algorithmica 1:49\u201363","journal-title":"Algorithmica"},{"key":"BF01928918_CR3","unstructured":"Baker B (1985) Shortest paths with unit clearance among polygonal obstacles. SIAM Conference on Geometrical Modelling and Robotics"},{"key":"BF01928918_CR4","doi-asserted-by":"crossref","unstructured":"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\u201348","DOI":"10.1109\/SFCS.1987.1"},{"key":"BF01928918_CR5","doi-asserted-by":"crossref","unstructured":"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\u201360","DOI":"10.1109\/SFCS.1987.42"},{"key":"BF01928918_CR6","unstructured":"Chew LP (1987) Planar graphs and sparse graphs for efficient motion planning in the plane. Manuscript"},{"key":"BF01928918_CR7","doi-asserted-by":"crossref","unstructured":"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\u2013220","DOI":"10.1145\/323233.323261"},{"key":"BF01928918_CR8","doi-asserted-by":"crossref","unstructured":"Clarkson K (1987) Approximation algorithms for shortest path motion planning. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp 56\u201365","DOI":"10.1145\/28395.28402"},{"key":"BF01928918_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013257","DOI":"10.1145\/41958.41985"},{"key":"BF01928918_CR10","unstructured":"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\u2013183"},{"key":"BF01928918_CR11","doi-asserted-by":"crossref","unstructured":"Edelsbrunner H (1987) Algorithms in combinatorial geometry. Springer-Verlag","DOI":"10.1007\/978-3-642-61568-9"},{"key":"BF01928918_CR12","doi-asserted-by":"crossref","unstructured":"Edelsbrunner H, Guibas L (1986) Topologically sweeping in an arrangement. In: Proceedings of the 18th ACM Symposium on Theory of Consumpting, pp 389\u2013403","DOI":"10.1145\/12130.12171"},{"key":"BF01928918_CR13","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M Fredman","year":"1987","unstructured":"Fredman M, Tarjan R (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J of the Association for Computing Machinery 34:596\u2013615","journal-title":"J of the Association for Computing Machinery"},{"key":"BF01928918_CR14","doi-asserted-by":"crossref","unstructured":"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\u201319","DOI":"10.1109\/SFCS.1987.6"},{"key":"BF01928918_CR15","doi-asserted-by":"crossref","unstructured":"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\u201363","DOI":"10.1145\/41958.41964"},{"key":"BF01928918_CR16","unstructured":"Hershberger JE (1987) Efficient algorithms for shortest path and visibility problems. Dissertation, Stanford University"},{"key":"BF01928918_CR17","unstructured":"Hershberger JE, Guibas LJ (1986) AnO(n 2 ) shortest path algorithm for a non-rotating convex body. Technical Report, DEC Systems Research Center"},{"key":"BF01928918_CR18","volume-title":"Dissertation","author":"DT Lee","year":"1978","unstructured":"Lee DT (1978) Proximity and reachability in the plane. Dissertation, University of Illinois at Urbana-Champaign"},{"key":"BF01928918_CR19","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"DT Lee","year":"1984","unstructured":"Lee DT, Preparata FP (1984) Euclidean shortest paths in the presence of rectilinear barriers. Networks 14:393\u2013410","journal-title":"Networks"},{"key":"BF01928918_CR20","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","volume":"22","author":"T Lozano-Perez","year":"1979","unstructured":"Lozano-Perez T, Wesley MA (1979) An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM 22:560\u2013570","journal-title":"Communications of the ACM"},{"key":"BF01928918_CR21","unstructured":"Masser M (1988) Algorithmen zur Konstruktion von Sichtbarkeitsgraphen. Diplomarbeit, Institutes for Information Processing, IIG, Technical University of Graz, in preparation"},{"key":"BF01928918_CR22","doi-asserted-by":"crossref","unstructured":"Mehlhorn K (1984) Data structures and algorithms 2: graph algorithms and NP-completeness. Springer-Verlag","DOI":"10.1007\/978-3-642-69897-2"},{"key":"BF01928918_CR23","doi-asserted-by":"crossref","unstructured":"Mehlhorn K (1984) Data structures and algorithms 3: multidimensional searching and computational geometry. Springer-Verlag","DOI":"10.1007\/978-3-642-69900-9"},{"key":"BF01928918_CR24","doi-asserted-by":"crossref","unstructured":"Mitchell JSB, Papadimitriou CH (1987) The weighted region problem. In: Proceedings of the 3rd Annual Symposium on Computational Geometry, pp 30\u201338","DOI":"10.1145\/41958.41962"},{"key":"BF01928918_CR25","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/0216045","volume":"23","author":"JSB Mitchel","year":"1987","unstructured":"Mitchel JSB, Mount DM, Papadimitriou CH (1987) The discrete geodesic problem. SIAM J Computing 23:647\u2013668","journal-title":"SIAM J Computing"},{"key":"BF01928918_CR26","unstructured":"Overmars M, Welzl E (1987) Construction of sparse visibility graphs. Report RUU-CS-87-9, Department of Computer Science, University of Utrecht"},{"key":"BF01928918_CR27","doi-asserted-by":"crossref","unstructured":"Overmars M, Welzl E (1988) New methods for computing visibility graphs. To appear in: Proceedings of the 4th Annual Symposium on Computational Geometry","DOI":"10.1145\/73393.73410"},{"key":"BF01928918_CR28","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0020-0190(85)90029-8","volume":"20","author":"CH Papadimitriou","year":"1985","unstructured":"Papadimitriou CH (1985) An algorithm for shortest path motion in three dimensions. Inform Process Lett 20:259\u2013263","journal-title":"Inform Process Lett"},{"key":"BF01928918_CR29","unstructured":"Papadimitriou CH, Silverberg EB (1986) Optimal piecewise linear motion of an object among obstacles. Technical Report, Dept. of Operations Research, Stanford University"},{"key":"BF01928918_CR30","doi-asserted-by":"crossref","unstructured":"Preparata FP, Shamos MI (1985) Computational geometry. Springer Verlag","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"BF01928918_CR31","unstructured":"Reif J, Storer JA (1985) Shortest paths in Euclidean space with polyhedral obstacles. Technical Report CS-85-121, Computer Science Department, Brandeis University"},{"key":"BF01928918_CR32","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0020-0190(86)90045-1","volume":"23","author":"H Rohner","year":"1986","unstructured":"Rohner H (1986) Shortest paths in the plane with convex polygonal obstacles. Inform Process Lett 23:71\u201376","journal-title":"Inform Process Lett"},{"key":"BF01928918_CR33","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0215014","volume":"15","author":"A Schorr","year":"1986","unstructured":"Schorr A, Sharir M (1986) On shortest paths in polyhedral spaces. SIAM J Computing 15:193\u2013215","journal-title":"SIAM J Computing"},{"key":"BF01928918_CR34","doi-asserted-by":"crossref","unstructured":"Tarjan RE, van Wyk C (1986) AnO(n log log n)-time algorithm for triangulating simple polygons. Manuscript","DOI":"10.1145\/12130.12170"},{"key":"BF01928918_CR35","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0020-0190(85)90044-4","volume":"20","author":"E Welzl","year":"1985","unstructured":"Welzl E (1985) Constructing the visibility graph forn line segments inO(n 2) time. Inform Process Lett 20:167\u2013171","journal-title":"Inform Process Lett"}],"container-title":["Zeitschrift f\u00fcr Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01928918.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01928918\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01928918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T05:56:29Z","timestamp":1586325389000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01928918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,5]]},"references-count":35,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1988,5]]}},"alternative-id":["BF01928918"],"URL":"https:\/\/doi.org\/10.1007\/bf01928918","relation":{},"ISSN":["0340-9422","1432-5217"],"issn-type":[{"type":"print","value":"0340-9422"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[1988,5]]}}}