{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T06:28:14Z","timestamp":1764570494980},"publisher-location":"Berlin, Heidelberg","reference-count":57,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540554882"},{"type":"electronic","value":"9783540471035"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55488-2_26","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:07:51Z","timestamp":1330250871000},"page":"148-185","source":"Crossref","is-referenced-by-count":2,"title":["Restricted orientation computational geometry"],"prefix":"10.1007","author":[{"given":"Bengt J.","family":"Nilsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Ottmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Schuierer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Icking","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,29]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"M. Bern. Hidden surface removal for rectangles. In Proc. 29th ACM Symposium on Theory of Computing, pages 183\u2013192, 1988.","DOI":"10.1145\/73393.73412"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0022-0000(90)90018-G","volume":"40","author":"M. Bern","year":"1990","unstructured":"M. Bern. Hidden surface removal for rectangles. Journal of Comp. Syst. Sciences, 40:49\u201360, 1990.","journal-title":"Journal of Comp. Syst. Sciences"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1109\/TIT.1984.1056845","volume":"IT-30","author":"B. K. Bhattachara","year":"1984","unstructured":"B. K. Bhattachara and H. El Gindy. A new linear convex hull algorithm for simple polygons. IEEE Transactions on Information Theory, IT-30:85\u201388, 1984.","journal-title":"IEEE Transactions on Information Theory"},{"key":"8_CR4","unstructured":"J.F. Canny. The Complexity of Robot Motion Planning. PhD thesis, MIT, 1987. Published by MIT Press in the Series: ACM Doctoral Dissertation Awards, 1987."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"K.L. Clarkson, S. Kapoor, and P.M. Vaidya. Rectilinear shortest paths through polygonal obstacles in O(n log 2 n) time. In Proc. 3rd ACM Symp. on Computational Geometry, pages 251\u2013257, 1987.","DOI":"10.1145\/41958.41985"},{"key":"8_CR6","volume-title":"Technical Report TR 89-6","author":"J. Culberson","year":"1989","unstructured":"J. Culberson and R. Reckhow. A Unified Approach to Orthogonal Polygon Covering Problems via Dent Diagrams, Technical Report TR 89-6, Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, February 1989."},{"issue":"1","key":"8_CR7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0925-7721(91)90010-C","volume":"1","author":"M. Berg de","year":"1991","unstructured":"M. de Berg. On rectilinear link distance. Computational Geometry: Theory and Applications, 1(1): 13\u201334, 1991.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"M. de Berg and M. H. Overmans. Hidden surface removal for axis-parallel polyhedra. In Proc. 31st IEEE Symp. on Foundations of Computer Science, pages 252\u2013261, 1990.","DOI":"10.1109\/FSCS.1990.89544"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. van Kreveld, B.J. Nilsson, and M. Overmars. Finding shortest paths in the presence of orthogonal obstacles using a combined L1 and link metric. In Proc. 2nd Scandinavian Workshop on Algorithm Theory, pages 213\u2013224, Springer Verlag, Lecture Notes in Computer Science 447, 1990.","DOI":"10.1007\/3-540-52846-6_91"},{"key":"8_CR10","first-page":"215","volume":"XXXI","author":"E. Degreef","year":"1979","unstructured":"E. Degreef. Pasting and folding convexity spaces. Bulletin de la Societ\u00e9 Mathematique du Belgique, XXXI(Fasc. II-Ser. B):215\u2013230, 1979.","journal-title":"Bulletin de la Societ\u00e9 Mathematique du Belgique"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E.W. Dijkstra. A note on two problems in connection with graphs. Numer. Math., 1:269\u2013271, 1959.","journal-title":"Numer. Math."},{"key":"8_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02187714","volume":"4","author":"P. J. Rezende de","year":"1989","unstructured":"P.J. de Rezende, D.T. Lee, and Y.F. Wu. Rectilinear shortest paths with rectangular barriers. Journal of Discrete and Computational Geometry, 4:41\u201353, 1989.","journal-title":"Journal of Discrete and Computational Geometry"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L.J. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision. SIAM Journal of Computing, 15(2):317\u2013340, 1986.","journal-title":"SIAM Journal of Computing"},{"key":"8_CR14","unstructured":"H. ElGindy and P. Mitra. Orthogonal shortest route queries among axes parallel rectangular obstacles. 1991. Manuscript."},{"key":"8_CR15","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0734-189X(84)90142-7","volume":"28","author":"H. Edelsbrunner","year":"1984","unstructured":"H. Edelsbrunner, M.H. Overmars, and R. Seidel. Some methods of computational geometry applied to computer graphics. Computer Vision, Graphics, and Image Processing, 28:92\u2013108, 1984.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. In Proc. 25th IEEE Symp. on Foundations of Computer Science, pages 338\u2013346, 1984.","DOI":"10.1109\/SFCS.1984.715934"},{"key":"8_CR17","first-page":"689","volume":"443","author":"M. T. Goodrich","year":"1990","unstructured":"M. T. Goodrich, M. J. Atallah, and M. H. Overmars. An input-size\/outputsize trade off in the time-complexity of hidden surface removal. In Proc. 17th International Colloquium on Automata, Languages, and Programming, LNCS 443, pages 689\u2013702, 1990.","journal-title":"LNCS"},{"key":"8_CR18","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/S0734-189X(87)80114-7","volume":"40","author":"R. H. G\u00fcting","year":"1987","unstructured":"R. H. G\u00fcting and Th. Ottmann. New algorithms for special cases of the hidden line elimination problem. Computer Vision, Graphics, and Image Processing, 40:188\u2013204, 1987.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0020-0190(83)90010-8","volume":"16","author":"R. H. G\u00fcting","year":"1983","unstructured":"R. H. G\u00fcting. Stabbing c-oriented polygons. Information Processing Letters, 16:35\u201340, 1983.","journal-title":"Information Processing Letters"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0019-9958(84)80011-X","volume":"63","author":"R. H. G\u00fcting","year":"1984","unstructured":"R. H. G\u00fcting. Dynamic c-oriented polygonal intersection searching. Information und Control, 63:143\u2013163, 1984.","journal-title":"Information und Control"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/0196-6774(83)90013-5","volume":"4","author":"R. L. Graham","year":"1983","unstructured":"R. L. Graham and F. F. Yao. Finding the convex hull of a simple polygon. Journal of Algorithms, 4:324\u2013331, 1983.","journal-title":"Journal of Algorithms"},{"key":"8_CR22","unstructured":"C. Icking. K\u00fcrzeste Pfade mit Hindernissen bei festen Orienterungen. September 1988. Unpublished Manuscript, Presented at the Freie Universit\u00e4t Berlin."},{"key":"8_CR23","series-title":"Lecture Notes in Pure and Applied Mathematics 76","first-page":"113","volume-title":"Convexity and Related Combinatorial Geometry, Proceedings of the 2nd University of Oklahoma Conference","author":"R. E. Jamison-Waldner","year":"1982","unstructured":"R. E. Jamison-Waldner. A perspective on abstract convexity: classifying alignments by varieties. In D. C. Kay and M. Breen, editors, Convexity and Related Combinatorial Geometry, Proceedings of the 2 nd University of Oklahoma Conference, pages 113\u2013150, Marcel Dekker, Inc., New York and Basel, 1982. Lecture Notes in Pure and Applied Mathematics 76."},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"D.B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 1\u201313, 1977.","DOI":"10.1145\/321992.321993"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"J. M. Keil. Minimally covering a horizontally convex polygon. In Proc. 2nd ACM Symp. on Computational Geometry, pages 43\u201351, 1986.","DOI":"10.1145\/10515.10520"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. G. Kirkpatrick","year":"1983","unstructured":"D.G. Kirkpatrick. Optimal search in planar subdivision. SIAM Journal of Computing, 12:28\u201335, 1983.","journal-title":"SIAM Journal of Computing"},{"key":"8_CR27","doi-asserted-by":"crossref","first-page":"471","DOI":"10.2140\/pjm.1971.38.471","volume":"38","author":"D. C. Kay","year":"1971","unstructured":"D. C. Kay and E. W. Womble. Axiomatic convexity theory and the relationship between the Carath\u00e9odory, Helly and Radon numbers. Pacific Journal of Mathematics, 38:471\u2013485, 1971.","journal-title":"Pacific Journal of Mathematics"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"D.T. Lee, T.H. Chen, and C.D. Yang. Shortest rectilinear paths among weighted obstacles. In Proc. 6th ACM Symp. on Computational Geometry, pages 301\u2013310, 1990.","DOI":"10.1145\/98524.98595"},{"key":"8_CR29","first-page":"65","volume":"15","author":"F. W. Levi","year":"1951","unstructured":"F. W. Levi. On Helly's theorem and the axioms of convexity. Journal of the Indian Mathematical Society, 15:65\u201376, 1951.","journal-title":"Journal of the Indian Mathematical Society"},{"key":"8_CR30","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/net.3230110307","volume":"11","author":"R. C. Larson","year":"1981","unstructured":"R.C. Larson and V.O. Li. Finding minimum rectilinear distance paths in the presence of barriers. Networks, 11:285\u2013304, 1981.","journal-title":"Networks"},{"key":"8_CR31","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D. T. Lee","year":"1984","unstructured":"D.T. Lee and F.P. Preparata, Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14:393\u2013410, 1984.","journal-title":"Networks"},{"key":"8_CR32","doi-asserted-by":"crossref","unstructured":"R.J. Lipton and R.E. Tarjan. A separator theorem for planar graphs. SIAM Journal of Numerical Analysis, 177\u2013189, 1979.","DOI":"10.1137\/0136016"},{"key":"8_CR33","unstructured":"D. Y. Montuno and A. Fournier. Finding the X-Y Convex Hull of A Set of X-Y Polygons. Technical Report CSRG-148, Univerity of Toronto, 1982."},{"key":"8_CR34","unstructured":"K.M. McDonald and J.G. Peters. Smallest Paths in Simple Rectilinear Polygons. Technical Report TR 89-4, School of Computing Science, Simon Fraser University, 1989."},{"key":"8_CR35","doi-asserted-by":"crossref","unstructured":"R. Motwani, A. Raghunathan, and H. Saran. Covering orthogonal polygons with star polygons: the perfect graph approach. In Proc. 4th ACM Symp. on Computational Geometry, pages 211\u2013223, 1988.","DOI":"10.1145\/73393.73415"},{"key":"8_CR36","doi-asserted-by":"crossref","unstructured":"R. Motwani, A. Raghunathan, and H. Saran. Perfect graphs and orthogonally convex covers. In Fourth Annual SIAM Conference on Discrete Mathematics, 1988.","DOI":"10.1137\/0402033"},{"key":"8_CR37","first-page":"157","volume":"33","author":"T. M. Nicholl","year":"1984","unstructured":"T. M. Nicholl, D. T. Lee, Y. Z. Liao, and C. K. Wong. Constructing the x-y convex hull of a set of x-y polygons. BIT, 33:157\u2013171, 1984.","journal-title":"BIT"},{"key":"8_CR38","doi-asserted-by":"crossref","unstructured":"M. H. Overmars and M. Sharir. Output-sensitive hidden surface removal. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 19\u201328, 1989.","DOI":"10.1109\/SFCS.1989.63541"},{"key":"8_CR39","doi-asserted-by":"crossref","unstructured":"Th. Ottmann, E. Soisalon-Soininen, and D. Wood. On the definition and computation of rectilinear convex hulls. Information Sciences, 33, 1984.","DOI":"10.1016\/0020-0255(84)90025-2"},{"key":"8_CR40","doi-asserted-by":"crossref","unstructured":"F.P. Preparata and M.I. Shamos. Computational Geometry \u2014 an Introduction. Springer Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"8_CR41","first-page":"71","volume":"447","author":"F. P. Preparata","year":"1990","unstructured":"F. P. Preparata, J. S. Vitter, and M. Yvinec. Output-sensitive generation of the perspective view of isothetic parallelepipeds. In Proc. 2nd Scandinavian Workshop on Algorithm Theory, LNCS 447, pages 71\u201384, 1990.","journal-title":"LNCS"},{"key":"8_CR42","unstructured":"G. Rawlins. Explorations in Restricted-Orientation Geometry. PhD thesis, University of Waterloo, 1987."},{"key":"8_CR43","doi-asserted-by":"crossref","unstructured":"R. Reckhow and J. Culberson. Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons. In Proc. 3rd ACM Symp. on Computational Geometry, pages 268\u2013277, 1987.","DOI":"10.1145\/41958.41987"},{"key":"8_CR44","unstructured":"R. Reckhow. Covering Orthogonally Convex Polygons with Three Orientations of Dents. Technical Report TR87-17, University of Alberta, 1987."},{"key":"8_CR45","volume-title":"Technical Report \u201cBericht 39\u201d","author":"G. Reich","year":"1991","unstructured":"G. Reich. Finitely-Oriented Shortest Paths in the Presence of Polygonal Obstacles. Technical Report \u201cBericht 39\u201d, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, Germany, October 1991."},{"key":"8_CR46","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0890-5401(87)90045-9","volume":"72","author":"G. Rawlins","year":"1987","unstructured":"G. Rawlins and D. Wood. On the optimal computation of finitely-oriented convex hulls. Information and Computation, 72:150\u2013166, 1987.","journal-title":"Information and Computation"},{"key":"8_CR47","first-page":"137","volume-title":"Computational Morphology","author":"G. Rawlins","year":"1988","unstructured":"G. Rawlins and D. Wood. Ortho-convexity and its generalizations. In Godfried T. Toussaint, editor, Computational Morphology, pages 137\u2013152, Elsevier Science Publishers B. V., (North-Holland), 1988."},{"key":"8_CR48","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF01231029","volume":"36","author":"G. Rawlins","year":"1989","unstructured":"G. Rawlins and D. Wood. A decomposition theorem for convexity spaces. Journal of Geometry, 36:143\u2013159, 1989.","journal-title":"Journal of Geometry"},{"key":"8_CR49","unstructured":"G. Rawlins and D. Wood. Restricted-Oriented Convex Sets. Research Report CS-89-01, University of Waterloo, 1989."},{"key":"8_CR50","volume-title":"An optimal data structure for shortest rectilinear path queries in a simple polygon","author":"S. Schuierer","year":"1991","unstructured":"S. Schuierer. An optimal data structure for shortest rectilinear path queries in a simple polygon. 1991. Manuscript, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, Germany."},{"key":"8_CR51","first-page":"115","volume":"XXV","author":"G. Sierksma","year":"1977","unstructured":"G. Sierksma. Relationships between Carath\u00e9odory, Helly, Radon and Exchange numbers of convexity spaces. Nieuw Archief voor Wiskunde, XXV:115\u2013132, 1977.","journal-title":"Nieuw Archief voor Wiskunde"},{"key":"8_CR52","volume-title":"Data Structuring Group Research Report CS-89-48","author":"S. Schuierer","year":"1989","unstructured":"S. Schuierer, G. Rawlins, and D. Wood. Visibility, Skulls, and Kernels in Convexity Spaces. Data Structuring Group Research Report CS-89-48, University of Waterloo, Ontario, Canada, October 1989."},{"key":"8_CR53","doi-asserted-by":"crossref","unstructured":"S. Schuierer, G. Rawlins, and D. Wood. A generalization of staircase visibility. In H. Bieri, editor, Computational Geometry\u2014Methods, Algorithms, and Applications, LNCS 553, pages 277-288, Springer-Verlag, 1991.","DOI":"10.1007\/3-540-54891-2_21"},{"key":"8_CR54","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R.E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669\u2013679, 1986.","journal-title":"Communications of the ACM"},{"key":"8_CR55","unstructured":"S. Schuierer and D. Wood. Restricted Orientation Visibility. Technical Report 40, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, 1991."},{"key":"8_CR56","volume-title":"Technical Report \u201cBericht 19\u201d","author":"P. Widmayer","year":"1990","unstructured":"P. Widmayer. On Shortest Paths in VLSI design. Technical Report \u201cBericht 19\u201d, Institut f\u00fcr Informatik, Universit\u00e4t Freiburg, Germany, March 1990. Also to appear in: Annals of Operations Research, 1991."},{"key":"8_CR57","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1137\/0216049","volume":"16","author":"P. Widmayer","year":"1987","unstructured":"P. Widmayer, Y.F. Wu, and C.K. Wong. On some distance problems in fixed orientations. SIAM Journal of Computing, 16:728\u2013746, 1987.","journal-title":"SIAM Journal of Computing"}],"container-title":["Lecture Notes in Computer Science","Data structures and efficient algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55488-2_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:59:09Z","timestamp":1605646749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55488-2_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540554882","9783540471035"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/3-540-55488-2_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}