{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:13:44Z","timestamp":1760440424831},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1995,7,1]],"date-time":"1995-07-01T00:00:00Z","timestamp":804556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,7]]},"DOI":"10.1007\/bf01300371","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T09:45:54Z","timestamp":1111743954000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["Staircase visibility and computation of kernels"],"prefix":"10.1007","volume":"14","author":[{"given":"S.","family":"Schuierer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees.Proc. 15th ACM Symp. on Theory of Computing, 1983, pp. 80?86.","DOI":"10.1145\/800061.808735"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1109\/TIT.1984.1056845","volume":"30","author":"B. Bhattachara","year":"1984","unstructured":"B. Bhattachara and H. El Gindy. A new linear convex hull algorithm for simple polygons.IEEE Transactions on Information Theory, 30:85?88, 1984.","journal-title":"IEEE Transactions on Information Theory"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"B. Chazelle and H. Edelsbrunner. An optimal algorithm to intersect line segments in the plane.Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 590?600.","DOI":"10.1109\/SFCS.1988.21975"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"R. Cole and M. Goodrich. Optimal parallel algorithms for polygon and point-set problems.Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 201?210.","DOI":"10.1145\/73393.73414"},{"key":"CR5","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, 1989."},{"key":"CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"L. Gewali and S. Ntafos. Minimum covers for grids and orthogonal polygons by periscope guards. In Jorge Urrutia, editor,Proc. 2nd Canadian Conf. on Computational Geometry, University of Ottawa, 1990, pp. 358?361.","DOI":"10.21236\/ADA225443"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/0196-6774(83)90013-5","volume":"4","author":"R. Graham","year":"1983","unstructured":"R. Graham and F. Yao. Finding the convex hull of a simple polygon.Journal of Algorithms, 4:324?331, 1983.","journal-title":"Journal of Algorithms"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"J. Keil. Minimally covering a horizontally convex polygon.Proc. 2nd ACM Symp. on Computational Geometry, 1986, pp. 43?51.","DOI":"10.1145\/10515.10520"},{"issue":"1","key":"CR10","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"12","author":"D. Kirkpatrick","year":"1986","unstructured":"D. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm.SIAM Journal of Computing, 12(1):287?299, 1986.","journal-title":"SIAM Journal of Computing"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF00993195","volume":"12","author":"D. Lee","year":"1983","unstructured":"D. Lee. On finding the convex hull of a simple polygon.International Journal of Computer and Information Sciences, 12:87?99, 1983.","journal-title":"International Journal of Computer and Information Sciences"},{"issue":"3","key":"CR12","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1145\/322139.322142","volume":"26","author":"D. Lee","year":"1979","unstructured":"D. Lee and F. Preparata. An optimal algorithm for finding the kernel of a polygon.Journal of the ACM, 26(3):415?421, 1979.","journal-title":"Journal of the ACM"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(79)90069-3","volume":"9","author":"D. McCallum","year":"1979","unstructured":"D. McCallum and D. Avis. A linear algorithm for finding the convex hull of a simple polygon.Information Processing Letters, 9:201?206, 1979.","journal-title":"Information Processing Letters"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"I. Munro, M. Overmars, and D. Wood. Variations on visibility.Proc. 3rd ACM Symp. on Computational Geometry, 1987, pp. 291?299.","DOI":"10.1145\/41958.41989"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"R. Motwani, A. Raghunathan, and H. Saran. Covering orthogonal polygons with star polygons: the perfect graph approach.Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 211?223.","DOI":"10.1145\/73393.73415"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"R. Motwani, A. Raghunathan, and H. Saran. Perfect graphs and orthogonally convex covers.Proc. 4th SIAM Conference on Discrete Mathematics, 1988.","DOI":"10.1137\/0402033"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1007\/BF01933620","volume":"23","author":"T. Nicholl","year":"1983","unstructured":"T. Nicholl, D. Lee, Y. Liao, and C. Wong. Constructing thex-y convex hull of a set ofx-y convex polygons.BIT, 23:456?471, 1983.","journal-title":"BIT"},{"key":"CR18","unstructured":"Th. Ottmann and P. Widmayer.Algorithmen und Datenstrukturen. BI Wissenschaftsverlag, 1990."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1016\/0196-6774(88)90028-4","volume":"9","author":"M. Overmars","year":"1988","unstructured":"M. Overmars and D. Wood. On rectangular visibility.Journal of Algorithms, 9:372?390, 1988.","journal-title":"Journal of Algorithms"},{"key":"CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry?an Introduction","author":"F. Preparata","year":"1985","unstructured":"F. Preparata and M. Shamos.Computational Geometry?an Introduction. Springer-Verlag New York, 1985."},{"key":"CR21","unstructured":"G. Rawlins. Explorations in Restricted-Orientation Geometry. Ph.D. thesis, University of Waterloo, 1987."},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"R. Reckhow and J. Culberson. Covering a simple orthogonal polygon with a minimum number of orthogonally convex polygons.Proc. 3rd ACM Symp. on Computational Geometry, 1987, pp. 268?277.","DOI":"10.1145\/41958.41987"},{"key":"CR23","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?166, 1987.","journal-title":"Information and Computation"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"G. Rawlins and D. Wood. Computational geometry with restricted orientations.Proc. 13th IFIP Conf. on System Modelling and Optimization, 1988.","DOI":"10.1007\/BFb0042806"},{"key":"CR25","first-page":"137","volume-title":"Computational Morphology","author":"G. Rawlins","year":"1988","unstructured":"G. Rawlins and D. Wood. Ortho-convexity and its generalizations. In G. Toussaint, editor,Computational Morphology, Elsevier (North-Holland), Amsterdam, 1988, pp. 137?152."},{"key":"CR26","unstructured":"R. Schneider. Convex geometry. Script to lecture, 1989."},{"key":"CR27","unstructured":"S. Schuierer and D. Wood. Restricted Orientation Visibility. Technical Report 40, Inst. f\u00fcr Informatik, Universit\u00e4t Freiburg, 1991."},{"key":"CR28","unstructured":"S. Schuierer and D. Wood. Visibility in Semi-Convex Spaces. Technical Report 37, Inst. f\u00fcr Informatik, Universit\u00e4t Freiburg, 1991."},{"issue":"4","key":"CR29","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02187918","volume":"3","author":"D. Wood","year":"1988","unstructured":"D. Wood and C. Yap. The orthogonal convex skull problem.Discrete & Computational Geometry, 3(4): 349?365, 1988.","journal-title":"Discrete & Computational Geometry"},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"A. Yao. Lower-bounds for algebraic computation trees with integer inputs.Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 308?313.","DOI":"10.1109\/SFCS.1989.63495"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01300371.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01300371\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01300371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T10:34:32Z","timestamp":1625654072000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01300371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,7]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,7]]}},"alternative-id":["BF01300371"],"URL":"https:\/\/doi.org\/10.1007\/bf01300371","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,7]]}}}