{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T05:21:09Z","timestamp":1648531269919},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1989,9,1]],"date-time":"1989-09-01T00:00:00Z","timestamp":620611200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[1989,9]]},"DOI":"10.1007\/bf00127827","type":"journal-article","created":{"date-parts":[[2004,11,2]],"date-time":"2004-11-02T23:51:56Z","timestamp":1099439516000},"page":"161-191","source":"Crossref","is-referenced-by-count":10,"title":["Dynamic computational geometry on meshes and hypercubes"],"prefix":"10.1007","volume":"3","author":[{"given":"Laurence","family":"Boxer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russ","family":"Miller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"Ametek, Inc. 1986. Ametek System 14 User's Guide (Aug.)."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1016\/0898-1221(85)90105-1","volume":"11","author":"M.J. Atallah","year":"1985","unstructured":"Atallah, M.J. 1985. Some dynamic computational geometry problems. Comp. and Maths. with Appls., 11:1171?1181.","journal-title":"Comp. and Maths. with Appls."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"Atallah, M.J., and Hambrusch, S.E. 1985. Solving tree problems on a mesh-connected processor array. In Proc., 26th Symposium on the Foundations of Computer Science, pp. 222?231.","DOI":"10.1109\/SFCS.1985.53"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1145\/828.322449","volume":"31","author":"M.J. Atallah","year":"1984","unstructured":"Atallah, M.J., and Kosaraju, S.R. 1984. Graph problems on a mesh-connected processor array. JACM, 31:649?667.","journal-title":"JACM"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"746","DOI":"10.1109\/TC.1968.229158","volume":"C-17","author":"G.H. Barnes","year":"1968","unstructured":"Barnes, G.H., Brown, R.M., Kato, M., Kuck, D.J., Slotnick, D.L., and Stokes, R.A. 1968. The ILLIAC IV computer. IEEE Trans. on Computers, C-17:746?757.","journal-title":"IEEE Trans. on Computers"},{"key":"CR6","first-page":"307","volume-title":"Proc., AFIPS Spring Joint Computer Conf., vol. 32","author":"K.E. Batcher","year":"1968","unstructured":"Batcher, K.E. 1968. Sorting networks and their applications. In Proc., AFIPS Spring Joint Computer Conf., vol. 32, AFIPS Press, New Jersey, pp. 307?314."},{"key":"CR7","unstructured":"Beetem, J., Denneau, M., and Weingarten, D. 1985. The GFll supercomputer. In Proc., Symposium on Computer Architecture, pp. 108?114."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Boxer, L., and Miller, R. 1989. Parallel dynamic computational geometry. J. of New Generation Computer Systems, to appear.","DOI":"10.1007\/BF00127827"},{"key":"CR9","unstructured":"Chandran, S., and Mount, D. 1989. Parallel computation of Davenport-Schinzel sequences. In Proc. of the 5th Annual ACM Symposium on Computational Geometry, to appear."},{"key":"CR10","unstructured":"Cypher, R., Sanz, J.L.C., and Snyder, L. 1987a. EREW PRAM and mesh-connected computer algorithms for image component labeling. In Proc., IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, pp. 122?128."},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"Cypher, R., Sanz, J.L.C., and Snyder, L. 1987b. Hypercube and shuffle-exchange algorithms for image component labeling. In Proc., IEEE Workshop on Computer Architecture for Pattern Analysis and Machine Intelligence, pp. 5?9.","DOI":"10.21236\/ADA197574"},{"issue":"3","key":"CR12","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1109\/34.21794","volume":"11","author":"R. Cypher","year":"1989","unstructured":"Cypher, R., Sanz, J.L.C., and Snyder, L. 1989. An EREW PRAM algorithm for image component labeling. IEEE Trans. on Pattern Analysis and Machine Intelligence, 11, 3 (Mar.), 258?262.","journal-title":"IEEE Trans. on Pattern Analysis and Machine Intelligence"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"684","DOI":"10.2307\/2373068","volume":"87","author":"H. Davenport","year":"1965","unstructured":"Davenport, H., and Schinzel, A. 1965. A combinatorial problem connected with differential equations. Amer. J. Math., 87:684?694.","journal-title":"Amer. J. Math."},{"issue":"6","key":"CR14","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0020-0190(86)90070-0","volume":"22","author":"F. Dehne","year":"1986","unstructured":"Dehne, F. 1986. O(n 1\/2) algorithms for the maximal element and ECDF searching problem on a mesh-connected computer. Information Processing Letters, 22, 6 (May), 303?306.","journal-title":"Information Processing Letters"},{"key":"CR15","unstructured":"Dehne, F., Hassenklover, A., Sack, J.-R., and Santoro, N. 1987. Parallel visibility on a mesh-connected computer. In Proc., International Conf. on Parallel Processing and Applications, pp. 173?178."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1093\/comjnl\/20.1.68","volume":"20","author":"M.L.B. Duff","year":"1977","unstructured":"Duff, M.L.B., and Watson, D.M. 1977. The cellular logic array image processor. Computer J., 20:68?72.","journal-title":"Computer J."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"Gustafson, J.L., Hawkinson, S., and Scott, K. 1986. The architecture of a homogeneous vector supercomputer. In Proc. of the International Conf. on Parallel Processing, pp. 649?652.","DOI":"10.1007\/BFb0116395"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"Hart, S., and Sharir, M. 1986. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica, 6:151?177.","journal-title":"Combinatorica"},{"key":"CR19","unstructured":"Hayes, J., Mudge, T.N., Stout, Q.F., Colley, S., and Palmer, J. 1986. Architecture of a hypercube supercomputer. In Proc. of the International Conf. on Parallel Processing, pp. 653?660."},{"key":"CR20","unstructured":"Hillis, D. 1985. The Connection Machine. MIT Press."},{"key":"CR21","unstructured":"Intel Corp. 1986. iPSC System Overview (Jan.)."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"1465","DOI":"10.1109\/PROC.1979.11496","volume":"67","author":"J.J. Koenderink","year":"1979","unstructured":"Koenderink, J.J., and Van Doom, A.J. 1979. New type of raster scan preserves the topology of the image. Proc. IEEE, 67:1465?1466.","journal-title":"Proc. IEEE"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TIT.1986.1057132","volume":"32","author":"A. Lempel","year":"1986","unstructured":"Lempel, A., and Ziv, J. 1986. Compression of two-dimensional data. IEEE Trans. Information Theory, 32:2?8.","journal-title":"IEEE Trans. Information Theory"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1109\/TPAMI.1985.4767645","volume":"PAMI-7","author":"R. Miller","year":"1985","unstructured":"Miller, R., and Stout, Q.F. 1985a. Geometric algorithms for digitized pictures on a mesh-connected computer. IEEE Trans. on PAMI, PAMI-7:216?228.","journal-title":"IEEE Trans. on PAMI"},{"key":"CR25","unstructured":"Miller, R., and Stout, Q.F. 1985b. Varying diameter and problem size in mesh-connected computers. In Proc. of the International Conf. on Parallel Processing, pp. 697?699."},{"key":"CR26","unstructured":"Miller, R., and Stout, Q.F. 1987. Graph and image processing algorithms for the hypercube. In Proc. of the SIAM Conf. on Hypercube Multiprocessors, pp. 418?425."},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"Miller, R., and Stout, Q.F. 1988a. Computational geometry on hypercube computers. In Proc. of the Third Conf. on Hypercube Concurrent Computers and Applications, pp. 1220?1229.","DOI":"10.1145\/63047.63076"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1109\/12.9737","volume":"37","author":"R. Miller","year":"1988","unstructured":"Miller, R., and Stout, Q.F. 1988b. Efficient parallel convex hull algorithms. IEEE Trans. on Computers, 37:1605?1618.","journal-title":"IEEE Trans. on Computers"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1109\/12.21120","volume":"38","author":"R. Miller","year":"1989","unstructured":"Miller, R., and Stout, Q.F. 1989a. Mesh computer algorithms for computational geometry. IEEE Trans. on Computers, 38:321?340.","journal-title":"IEEE Trans. on Computers"},{"key":"CR30","volume-title":"Parallel Algorithms for Regular Architectures","author":"R. Miller","year":"1989","unstructured":"Miller, R., and Stout, Q.F. 1989b. Parallel Algorithms for Regular Architectures. MIT Press, Cambridge, Mass., to appear."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1137\/0209058","volume":"9","author":"D. Nassimi","year":"1980","unstructured":"Nassimi, D., and Sahni, S. 1980. Finding connected components and connected ones on a mesh-connected parallel computer. SIAM J. Comput., 9:744?757.","journal-title":"SIAM J. Comput."},{"key":"CR32","volume-title":"The Massively Parallel Processor","year":"1985","unstructured":"Potter, J.L., ed. 1985. The Massively Parallel Processor. MIT Press, Cambridge, Mass."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1109\/TC.1984.1676459","volume":"C-33","author":"F.P. Preparata","year":"1984","unstructured":"Preparata, F.P., and Lee, D.T. 1984. Computational geometry?A survey. IEEE Trans. on Computers, C-33:1072?1100.","journal-title":"IEEE Trans. on Computers"},{"key":"CR34","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., and Shamos, M.I. 1985. Computational Geometry. Springer-Verlag, New York."},{"key":"CR35","unstructured":"Reddaway, S.F. 1978. DAP?A flexible number cruncher. In Proc., LASL Workshop on Vector Parallel Processors, pp. 233?234."},{"key":"CR36","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1145\/7531.7532","volume":"34","author":"J.H. Reif","year":"1987","unstructured":"Reif, J.H., and Valiant, L.G. 1987. A logarithmic time sort for linear size networks. JACM, 34:60?76.","journal-title":"JACM"},{"key":"CR37","volume-title":"Combinatorial Algorithms","author":"E.M. Reingold","year":"1977","unstructured":"Reingold, E.M., Nievergelt, J., and Deo, N. 1977. Combinatorial Algorithms. Prentice Hall, New York."},{"issue":"1","key":"CR38","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0743-7315(89)90045-2","volume":"6","author":"Y. Saad","year":"1989","unstructured":"Saad, Y., and Schultz, M.H. 1989. Data communication in hypercubes. J. of Parallel and Distributed Computing, 6, 1 (Feb.), 115?135.","journal-title":"J. of Parallel and Distributed Computing"},{"key":"CR39","unstructured":"Sanz, J.L.C., and Cypher, R.E. 1987. Data reduction and fast routing: A strategy for efficient algorithms for parallel message-passing computers. Tech. rept., Computer Science Dept., IBM Almaden Research Center."},{"key":"CR40","doi-asserted-by":"crossref","unstructured":"Shamos, M.I. 1975. Geometric complexity. In Proc., 7th Annual ACM Symposium on Theory of Computing, pp. 224?233.","DOI":"10.1145\/800116.803772"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02579209","volume":"7","author":"M. Sharir","year":"1987","unstructured":"Sharir, M. 1987. Almost linear upper bounds on the length of general Davenport-Schinzel sequences. Combinatorica, 7: 131?143.","journal-title":"Combinatorica"},{"key":"CR42","doi-asserted-by":"crossref","unstructured":"Slotnick, D.L., Borck, W.C., and McReynolds, R.C. 1962. The SOLOMON computer. In Proc. AFIPS Fall Joint Comp. Conf., pp. 97?107.","DOI":"10.1145\/1461518.1461528"},{"key":"CR43","doi-asserted-by":"crossref","unstructured":"Stout, Q.F. 1983. Topological matching. In Proc., 15th ACM Symposium on Theory of Computing, pp. 24?31.","DOI":"10.1145\/800061.808729"},{"key":"CR44","doi-asserted-by":"crossref","first-page":"213","DOI":"10.4064\/aa-25-2-213-224","volume":"25","author":"E. Szemeredi","year":"1974","unstructured":"Szemeredi, E. 1974. On a problem of Davenport and Schinzel. Acta Arith., 25: 213?224.","journal-title":"Acta Arith."},{"key":"CR45","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/359461.359481","volume":"20","author":"C.D. Thompson","year":"1977","unstructured":"Thompson, C.D., and Kung, H.T. 1977. Sorting on a mesh-connected parallel computer. Communications of the ACM, 20:263?271.","journal-title":"Communications of the ACM"},{"key":"CR46","volume-title":"Convex Figures","author":"I.M. Yaglom","year":"1961","unstructured":"Yaglom, I.M., and Boltyanskii, V.G. 1961. Convex Figures. Holt, Rinehart and Winston, New York."}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00127827.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00127827\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00127827","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T18:23:46Z","timestamp":1585938226000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00127827"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,9]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1989,9]]}},"alternative-id":["BF00127827"],"URL":"https:\/\/doi.org\/10.1007\/bf00127827","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,9]]}}}