{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T19:10:02Z","timestamp":1735758602276,"version":"3.32.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"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":[[1992,6]]},"DOI":"10.1007\/bf01758750","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T10:49:08Z","timestamp":1118832548000},"page":"25-49","source":"Crossref","is-referenced-by-count":20,"title":["Parallel computational geometry of rectangles"],"prefix":"10.1007","volume":"7","author":[{"given":"Sharat","family":"Chandran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sung Kwon","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01758750_CR1","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01762120","volume":"3","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. \u00d3'D\u00fanlaing, and C. Yap. Parallel computational geometry.Algorithmica, 3:293\u2013327, 1988.","journal-title":"Algorithmica"},{"key":"BF01758750_CR2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/0218035","volume":"18","author":"M. Atallah","year":"1989","unstructured":"M. Atallah, R. Cole, and M. Goodrich. Cascading divide-and-conquer: a technique for designing parallel algorithms.SIAM Journal on Computing, 18:499\u2013532, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"BF01758750_CR3","doi-asserted-by":"crossref","unstructured":"M. Atallah and M. Goodrich. Efficient plane sweeping in parallel. InProceedings of the Annual ACM Conference on Computational Geometry, pages 216\u2013226, 1986.","DOI":"10.1145\/10515.10539"},{"key":"BF01758750_CR4","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"29","author":"J. Bentley","year":"1980","unstructured":"J. Bentley and D. Wood. An optimal worst-case algorithm for reporting intersection of rectangles.IEEE Transactions on Computers, 29:571\u2013577, 1980.","journal-title":"IEEE Transactions on Computers"},{"key":"BF01758750_CR5","first-page":"362","volume-title":"Models for the Perception of Speech and Visual Form","author":"H. Blum","year":"1967","unstructured":"H. Blum. A transformation for extracting new descriptors ofshape. In W. Wathen-Dunn, editor,Models for the Perception of Speech and Visual Form, pages 362\u2013370. MIT Press, Cambridge, MA, 1967."},{"key":"BF01758750_CR6","unstructured":"Sharat Chandran. Merging in Parallel Computational Geometry. Ph.D. thesis, University of Maryland, 1989."},{"key":"BF01758750_CR7","unstructured":"S. Chandran and D. Mount. Shared memory algorithms and the medial axis transform. InProceedings of the 1987 Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, pages 44\u201350, 1987."},{"key":"BF01758750_CR8","doi-asserted-by":"crossref","unstructured":"R. Cole. Parallel merge sort. InProceedings of the IEEE Symposium on Foundations of Computer Science, pages 511\u2013516, 1986.","DOI":"10.1109\/SFCS.1986.41"},{"key":"BF01758750_CR9","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin. Deterministic coin tossing and accelerating cascades. InProceedings of the Annual ACM Symposium on Theory of Computing, pages 206\u2013219, 1986.","DOI":"10.1145\/12130.12151"},{"key":"BF01758750_CR10","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/359545.359553","volume":"21","author":"M. Fredman","year":"1978","unstructured":"M. Fredman and B. Weide. On the complexity of computing the measure \u222a [a i ,b i ].Communications of the ACM, 21:271\u2013291, 1978.","journal-title":"Communications of the ACM"},{"key":"BF01758750_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"L. Guibas","year":"1986","unstructured":"L. Guibas and B. Chazelle. Fractional cascading: I. A data structuring technique.Algorithmica, 1:133\u2013162, 1986.","journal-title":"Algorithmica"},{"key":"BF01758750_CR12","unstructured":"M. Goodrich. An output-sensitive algorithm for line segment intersection. InProceedings of the ACM Symposium on Parallel Algorithms and Architectures, pages 127\u2013136, 1989."},{"key":"BF01758750_CR13","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0196-6774(83)90044-5","volume":"4","author":"L. Guibas","year":"1983","unstructured":"L. Guibas and J. Saxe. Problem 80-15 and its solution.Journal of Algorithms, 4:177\u2013181, 1983.","journal-title":"Journal of Algorithms"},{"key":"BF01758750_CR14","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF00264251","volume":"21","author":"R. G\u00fcting","year":"1984","unstructured":"R. G\u00fcting. Optimal divide-and-conquer to compute the measure and contour for a set of iso-rectangles.Acta Informatica, 21:271\u2013291, 1984.","journal-title":"Acta Informatica"},{"key":"BF01758750_CR15","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H. Imai","year":"1983","unstructured":"H. Imai and T. Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane.Journal of Algorithms, 4:310\u2013323, 1983.","journal-title":"Journal of Algorithms"},{"key":"BF01758750_CR16","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1109\/TC.1985.6312202","volume":"34","author":"C. Kruskal","year":"1985","unstructured":"C. Kruskal, L. Rudolph, and M. Snir. The power of parallel prefix.IEEE Transactions on Computers, 34:965\u2013968, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"BF01758750_CR17","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0196-6774(80)90011-5","volume":"1","author":"W. Lipski","year":"1980","unstructured":"W. Lipski and F. Preparata. Finding the contour of a union of iso-oriented rectangles.Journal of Algorithms, 1:235\u2013246, 1980.","journal-title":"Journal of Algorithms"},{"key":"BF01758750_CR18","unstructured":"D. Moitra. Finding a minimal cover for binary images: an optimal parallel algorithm. InProceedings of the Allerton Conference on Communications, Control and Computing, pages 303\u2013313, 1988."},{"key":"BF01758750_CR19","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":"BF01758750_CR20","volume-title":"Picture Processing by Computer, Volume 2","author":"A. Rosenfeld","year":"1982","unstructured":"A. Rosenfeld and A. Kak.Picture Processing by Computer, Volume 2. Academic Press, New York, 1982."},{"key":"BF01758750_CR21","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/0196-6774(81)90027-4","volume":"2","author":"J. Leeuwen van","year":"1981","unstructured":"J. van Leeuwen and D. Wood. The measure problem for rectangular ranges ind-space.Journal of Algorithms, 2:282\u2013300, 1981.","journal-title":"Journal of Algorithms"},{"key":"BF01758750_CR22","first-page":"366","volume":"4","author":"Kiem-Phong Vo","year":"1982","unstructured":"Kiem-Phong Vo. Problem 80-4.Journal of Algorithms, 4:366\u2013367, 1982.","journal-title":"Journal of Algorithms"},{"key":"BF01758750_CR23","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/B978-0-444-87806-9.50020-7","volume-title":"Computational Geometry","author":"D. Wood","year":"1985","unstructured":"D. Wood. An isothetic view of computational geometry. In G. Toussaint, editor,Computational Geometry, pages 429\u2013459, North-Holland, Amsterdam, 1985."},{"key":"BF01758750_CR24","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0734-189X(88)90106-5","volume":"41","author":"A. Wu","year":"1988","unstructured":"A. Wu, S. K. Bhaskar, and A. Rosenfeld. Parallel computation of geometric properties from the medial axis transform.Computer Vision, Graphics and Image Processing, 41:323\u2013333, 1988.","journal-title":"Computer Vision, Graphics and Image Processing"},{"key":"BF01758750_CR25","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, C. Papadimitriou, and H. Kung. Locking policies: safety and freedom from deadlock. InProceedings of the IEEE Symposium on Foundations of Computer Science, pages 286\u2013297, 1979.","DOI":"10.1109\/SFCS.1979.22"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758750.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758750\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T18:29:03Z","timestamp":1735756143000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":25,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01758750"],"URL":"https:\/\/doi.org\/10.1007\/bf01758750","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}