{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T14:17:54Z","timestamp":1673360274469},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1996,6,1]],"date-time":"1996-06-01T00:00:00Z","timestamp":833587200000},"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":[[1996,6]]},"DOI":"10.1007\/bf01940884","type":"journal-article","created":{"date-parts":[[2005,7,27]],"date-time":"2005-07-27T15:12:55Z","timestamp":1122477175000},"page":"626-660","source":"Crossref","is-referenced-by-count":7,"title":["Connected component and simple polygon intersection searching"],"prefix":"10.1007","volume":"15","author":[{"given":"P. K.","family":"Agarwal","sequence":"first","affiliation":[]},{"given":"M.","family":"van Kreveld","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01940884_CR1","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF02187809","volume":"5","author":"P. K. Agarwal","year":"1991","unstructured":"P. K. Agarwal, Partitioning Arrangements of Lines: II. Applications,Discrete Comput. Geom. 5 (1991), 533\u2013573.","journal-title":"Discrete Comput. Geom."},{"key":"BF01940884_CR2","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1137\/0221035","volume":"21","author":"P. K. Agarwal","year":"1992","unstructured":"P. K. Agarwal, Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number,SIAM J. Comput. 21 (1992), 540\u2013570.","journal-title":"SIAM J. Comput."},{"key":"BF01940884_CR3","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1006\/jagm.1993.1040","volume":"15","author":"P. K. Agarwal","year":"1993","unstructured":"P. K. Agarwal, M. van Kreveld, and M. Overmars, Intersection Queries in Curved Objects,J. Algorithms 15 (1993), 229\u2013266.","journal-title":"J. Algorithms"},{"key":"BF01940884_CR4","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF02189304","volume":"9","author":"P. K. Agarwal","year":"1993","unstructured":"P. K. Agarwal and M. Sharir, Applications of aNew Space Partitioning Technique,Discrete Comp. Geom. 9 (1993), 11\u201338.","journal-title":"Discrete Comp. Geom."},{"key":"BF01940884_CR5","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF01285815","volume":"12","author":"B. Aronov","year":"1992","unstructured":"B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, Improved Bounds on the Complexity of Many Faces in Arrangements of Segments,Combinatorica 12 (1992), 261\u2013274.","journal-title":"Combinatorica"},{"key":"BF01940884_CR6","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01182772","volume":"11","author":"R. Yehuda Bar","year":"1994","unstructured":"R. Bar Yehuda and S. Fogel, Good Splitters with Applications to Ray Shooting,Algorithmica 11 (1994), 133\u2013145.","journal-title":"Algorithmica"},{"key":"BF01940884_CR7","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle, M. Sharir, and E. Welzl, Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems,Algorithmica 8 (1992), 407\u2013430.","journal-title":"Algorithmica"},{"key":"BF01940884_CR8","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1016\/0196-6774(92)90062-H","volume":"13","author":"S. W. Cheng","year":"1992","unstructured":"S. W. Cheng and R. Janardan, Algorithms for Ray-Shooting and Intersection Searching,J. Algorithms 13 (1992), 670\u2013692.","journal-title":"J. Algorithms"},{"key":"BF01940884_CR9","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest,Introduction to Algorithms, MIT Press, Cambridge, MA, 1990."},{"key":"BF01940884_CR10","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/128749.128750","volume":"39","author":"M. Dillencourt","year":"1992","unstructured":"M. Dillencourt, H. Samet, and M. Tammiuen, A General Approach to Connected Component Labeling for Arbitrary Image Representation,J. Assoc. Comput. Mach. 39 (1992), 253\u2013280.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01940884_CR11","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/0196-6774(87)90015-0","volume":"8","author":"D. P. Dobkin","year":"1987","unstructured":"D. P. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects,J. Algorithms 8 (1987), 348\u2013361.","journal-title":"J. Algorithms"},{"key":"BF01940884_CR12","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, Berlin, 1987."},{"key":"BF01940884_CR13","unstructured":"L. Guibas, Personal communication."},{"key":"BF01940884_CR14","unstructured":"L. Guibas, M. Overmars, and M. Sharir, Ray Shooting, Implicit Point Location, and Related Queries in Arrangements of Segments, Techn. Rep. No. 433, New York University, 1989."},{"key":"BF01940884_CR15","series-title":"Lecture Notes in Computer Science, Vol. 709","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/3-540-57155-8_262","volume-title":"Reporting and Dynamization","author":"J. Gupta","year":"1993","unstructured":"J. Gupta, R. Janardan, and M. Smid, Further Results on Generalized Intersection Searching Problems: Counting, Reporting and Dynamization,Proc. 3rd Workshop on Algorithms and Data Structures (1993), Lecture Notes in Computer Science, Vol. 709, Springer-Verlag, Berlin, pp. 361\u2013372."},{"key":"BF01940884_CR16","doi-asserted-by":"crossref","unstructured":"J. Gupta, R. Janardan, and M. Smid, Efficient Algorithms for Generalized Intersection Searching on Non-Iso-Oriented Objects,Proc. 10th ACM Symposium on Computational Geometry (1994), pp. 369\u2013378.","DOI":"10.1145\/177424.178096"},{"key":"BF01940884_CR17","first-page":"183","volume-title":"Lecture Notes in Computer Science, Vol. 824","author":"J. Gupta","year":"1994","unstructured":"J. Gupta, R. Janardan, and M. Smid, On Intersection Searching Involving Curved Objects,Proc. 4th Scand. Workshop on Algorithms Theory (1994), Lecture Notes in Computer Science, Vol. 824, Springer-Verlag, Berlin, pp. 183\u2013194."},{"key":"BF01940884_CR18","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H. Imai","year":"1984","unstructured":"H. Imai and T. Asano, Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane,J. Algorithms 4 (1984), 310\u2013323.","journal-title":"J. Algorithms"},{"key":"BF01940884_CR19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1142\/S021819599300004X","volume":"3","author":"R. Janardan","year":"1993","unstructured":"R. Janardan and M. Lopez, Generalized Intersection Searching Problems,Internat. J. Comput. Geom. Appl. 3 (1993), 39\u201370.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF01940884_CR20","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek, Range Searching with Efficient Hierarchical Cuttings,Discrete Comput. Geom. 10 (1993), 157\u2013182.","journal-title":"Discrete Comput. Geom."},{"key":"BF01940884_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69900-9","volume-title":"Data Structures and Algorithms 3: Multi-Dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn,Data Structures and Algorithms 3: Multi-Dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984."},{"key":"BF01940884_CR22","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1093\/comjnl\/36.2.107","volume":"36","author":"J. Nievergelt","year":"1993","unstructured":"J. Nievergelt and P. Widmayer, Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects,Comput. J. 36 (1993), 107\u2013116.","journal-title":"Comput. J."},{"key":"BF01940884_CR23","volume-title":"Lecture Notes in Computer Science, Vol. 156","author":"M. H. Overmars","year":"1983","unstructured":"M. H. Overmars,The Design of Dynamic Data Structures, Lecture Notes in Computer Science, Vol. 156, Springer-Verlag, Berlin, 1983."},{"key":"BF01940884_CR24","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF01931656","volume":"30","author":"M. H. Overmars","year":"1990","unstructured":"M. H. Overmars, H. Schipper, and M. Sharir, Storing Line Segments in Partition Trees, BIT 30 (1990), 385\u2013403.","journal-title":"BIT"},{"key":"BF01940884_CR25","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1145\/359131.359132","volume":"22","author":"F. P. Preparata","year":"1979","unstructured":"F. P. Preparata, A Real Time Algorithm for Convex Hull,Comm. ACM 22 (1979), 402\u2013405.","journal-title":"Comm. ACM"},{"key":"BF01940884_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry\u2014an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos,Computational Geometry\u2014an Introduction, Springer-Verlag, New York, 1985."},{"key":"BF01940884_CR27","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. Tarjan, Planar Point Location Using Persistent Search Trees,Comm. ACM 29 (1986), 609\u2013679.","journal-title":"Comm. ACM"},{"key":"BF01940884_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0747-7171(89)80002-1","volume":"7","author":"H. W. Sch\u00f6lten","year":"1989","unstructured":"H. W. Sch\u00f6lten and M. H. Overmars, General Methods for Adding Range Restrictions to Decomposable Searching Problems,J. Symbolic Comput. 7 (1989), 1\u201310.","journal-title":"J. Symbolic Comput."},{"key":"BF01940884_CR29","volume-title":"Davenport-Schinzel Sequences and Their Geometric Applications","author":"M. Sharir","year":"1995","unstructured":"M. Sharir and P. Agarwal,Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, New York, 1995."},{"key":"BF01940884_CR30","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan, Amortized Time Complexity,SIAM J. Discrete Math. 6 (1985), 306\u2013318.","journal-title":"SIAM J. Discrete Math."},{"key":"BF01940884_CR31","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1145\/3828.3839","volume":"32","author":"D. E. Willard","year":"1985","unstructured":"D. E. Willard and G. S. Lueker, Adding Range Restriction Capability to Dynamic Data Structures,J. Assoc. Comput. Mach. 32 (1985), 597\u2013617.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940884.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01940884\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01940884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T16:33:55Z","timestamp":1557765235000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01940884"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,6]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1996,6]]}},"alternative-id":["BF01940884"],"URL":"https:\/\/doi.org\/10.1007\/bf01940884","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,6]]}}}