{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T19:18:36Z","timestamp":1672255116884},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"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,1]]},"DOI":"10.1007\/bf01942608","type":"journal-article","created":{"date-parts":[[2005,7,26]],"date-time":"2005-07-26T16:24:55Z","timestamp":1122395095000},"page":"82-102","source":"Crossref","is-referenced-by-count":4,"title":["Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees"],"prefix":"10.1007","volume":"15","author":[{"given":"M. B.","family":"Dillencourt","sequence":"first","affiliation":[]},{"given":"H.","family":"Samet","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"BF01942608_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0734-189X(83)90017-8","volume":"24","author":"D. J. Abel","year":"1983","unstructured":"D. J. Abel and J. L. Smith. A data structure and algorithm based on a linear key for a rectangle retrieval problem.Computer Vision, Graphics, and Image Processing, 24(1):1\u201313, October 1983.","journal-title":"Computer Vision, Graphics, and Image Processing"},{"key":"BF01942608_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman.The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974."},{"key":"BF01942608_CR3","first-page":"179","volume":"2","author":"H. S. Baird","year":"1978","unstructured":"H. S. Baird. Fast algorithms for LSI artworks analysis.Journal of Design Automation & Fault-Tolerant Computing, 2:179\u2013209, 1978.","journal-title":"Journal of Design Automation & Fault-Tolerant Computing"},{"key":"BF01942608_CR4","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees.Proceedings of the Fifteenth Annual ACM Symposium on the Theory of Computing, pp. 80\u201386, Boston, MA, April 1983.","DOI":"10.1145\/800061.808735"},{"key":"BF01942608_CR5","volume-title":"Algorithms for Klee's rectangle problems","author":"J. L. Bentley","year":"1977","unstructured":"J. L. Bentley. Algorithms for Klee's rectangle problems. Unpublished manuscript, Computer Science Department, Carnegie-Mellon University, Pittsburgh, PA, 1977."},{"issue":"7","key":"BF01942608_CR6","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"29","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley and D. Wood. An optimal worst-case algorithm for reporting intersections of rectangles.IEEE Transactions on Computers, 29(7):571\u2013576, July 1980.","journal-title":"IEEE Transactions on Computers"},{"issue":"3","key":"BF01942608_CR7","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/128749.128750","volume":"39","author":"M. B. Dillencourt","year":"1992","unstructured":"M. B. Dillencourt, H. Samet, and M. Tamminen. A general approach to connected-component labeling for arbitrary image representations.Journal of the ACM, 39(3):253\u2013280, April 1992. Also see Corrigenda,Journal of the ACM, 39(4):985\u2013985, October 1992.","journal-title":"Journal of the ACM"},{"issue":"3","key":"BF01942608_CR8","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/358826.358838","volume":"23","author":"C. R. Dyer","year":"1980","unstructured":"C. R. Dyer, A. Rosenfeld, and H. Samet. Region representation: Boundary codes from quadtrees.Communications of the ACM, 23(3):171\u2013179, March 1980.","journal-title":"Communications of the ACM"},{"issue":"3\u20134","key":"BF01942608_CR9","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1080\/00207168308803364","volume":"13","author":"H. Edelsbrunner","year":"1983","unstructured":"H. Edelsbrunner. A new approach to rectangle intersections: part I.International Journal of Computer Mathematics, 13(3\u20134):209\u2013219, 1983.","journal-title":"International Journal of Computer Mathematics"},{"key":"BF01942608_CR10","volume-title":"EATCS Monographs on Theoretical Computer Science, vol. 10","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer-Verlag, Berlin, 1987."},{"key":"BF01942608_CR11","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement.Proceedings of the Eighteenth Annual ACM Symposium on the Theory of Computing, pp. 389\u2013403, Berkeley, CA, May 1986.","DOI":"10.1145\/12130.12171"},{"issue":"1","key":"BF01942608_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1145\/356625.356627","volume":"6","author":"H. Freeman","year":"1974","unstructured":"H. Freeman. Computer processing of line-drawing images.ACM Computing Surveys, 6(1):57\u201397, March 1974.","journal-title":"ACM Computing Surveys"},{"issue":"12","key":"BF01942608_CR13","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1145\/358728.358741","volume":"25","author":"I. Gargantini","year":"1982","unstructured":"I. Gargantini. An effective way to represent quadtrees.Communications of the ACM, 25(12):905\u2013910, December 1982.","journal-title":"Communications of the ACM"},{"issue":"4","key":"BF01942608_CR14","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1109\/TPAMI.1983.4767407","volume":"5","author":"E. Kawaguchi","year":"1983","unstructured":"E. Kawaguchi, T. Endo, and J. Matsunaga. Depth-first picture expression viewed from digital picture processing.IEEE Transactions on Pattern Analysis andMachine Intelligence, 5(4):373\u2013384, July 1983.","journal-title":"IEEE Transactions on Pattern Analysis andMachine Intelligence"},{"key":"BF01942608_CR15","series-title":"Advances in Computing Research, vol. 1","first-page":"91","volume-title":"Computational Geometry","author":"D. T. Lee","year":"1983","unstructured":"D. T. Lee. Maximum clique problem of rectangle graphs. In F. P. Preparata, editor,Computational Geometry, pp. 91\u2013107. Advances in Computing Research, vol. 1. JAI Press, Greenwich, CT, 1983."},{"issue":"2","key":"BF01942608_CR16","first-page":"257","volume":"14","author":"E. M. McCreight","year":"1985","unstructured":"E. M. McCreight. Priority search trees.S1AM Journal on Computing, 14(2):257\u2013276, May 1985.","journal-title":"S1AM Journal on Computing"},{"issue":"10","key":"BF01942608_CR17","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1145\/358656.358681","volume":"25","author":"J. Nievergelt","year":"1982","unstructured":"J. Nievergelt and F. P. Preparata. Plane-sweep algorithms for intersecting geometric figures.Communications of the ACM, 25(10):739\u2013747, October 1982.","journal-title":"Communications of the ACM"},{"key":"BF01942608_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos.Computational Geometry: An Introduction. Springer-Verlag, New York, 1985."},{"issue":"2","key":"BF01942608_CR19","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/50020.50021","volume":"20","author":"H. Samet","year":"1988","unstructured":"H. Samet. Hierarchical representations of collections of small rectangles.ACM Computing Surveys, 20(2):271\u2013309, December 1988.","journal-title":"ACM Computing Surveys"},{"key":"BF01942608_CR20","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H. Samet","year":"1990","unstructured":"H. Samet.The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990."},{"issue":"3","key":"BF01942608_CR21","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1109\/TPAMI.1985.4767646","volume":"7","author":"H. Samet","year":"1985","unstructured":"H. Samet and M. Tamminen. Computing geometric properties of images represented by linear quadtrees.IEEE Transactions on Pattern Analysis and Machine Intelligence, 7(3):229\u2013240, March 1985.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"4","key":"BF01942608_CR22","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1109\/34.3918","volume":"10","author":"H. Samet","year":"1988","unstructured":"H. Samet and M. Tamminen. Efficient component labeling of images of arbitrary dimension represented by linear bintrees.IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(4):579\u2013586, July 1988.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"3","key":"BF01942608_CR23","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1145\/282957.282966","volume":"4","author":"H. Samet","year":"1985","unstructured":"H. Samet and R. E. Webber. Storing a collection of polygons using quadtrees.ACM Transactions on Graphics, 4(3):182\u2013222, July 1985.","journal-title":"ACM Transactions on Graphics"},{"issue":"1","key":"BF01942608_CR24","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/0734-189X(84)90138-5","volume":"28","author":"M. Tamminen","year":"1984","unstructured":"M. Tamminen, Encoding pixel trees.Computer Graphics, Vision, and Image Processing, 28(1):44\u201357, October 1984.","journal-title":"Computer Graphics, Vision, and Image Processing"},{"issue":"2","key":"BF01942608_CR25","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan, Efficiency of a good but not linear set union algorithm.Journal of the ACM, 22(2):215\u2013225, April 1975.","journal-title":"Journal of the ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01942608.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01942608\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01942608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T12:40:06Z","timestamp":1557751206000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01942608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["BF01942608"],"URL":"https:\/\/doi.org\/10.1007\/bf01942608","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,1]]}}}