Abstract
Parallel algorithms are given for determining geometric properties of systems of moving point-objects. The objects are assumed to be moving in a Euclidean space such that each coordinate of a point's motion is a polynomial of bounded degree in the time variable. The properties investigated include nearest (farthest) neighbor, closest (farthest) pair, collision, convex hull, diameter, and containment. Several of these properties are investigated from both the dynamic and steady-state points of view. Efficient, and often optimal, implementations of these algorithms are given for the mesh and hypercube.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ametek, Inc. 1986. Ametek System 14 User's Guide (Aug.).
Atallah, M.J. 1985. Some dynamic computational geometry problems. Comp. and Maths. with Appls., 11:1171–1181.
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.
Atallah, M.J., and Kosaraju, S.R. 1984. Graph problems on a mesh-connected processor array. JACM, 31:649–667.
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.
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.
Beetem, J., Denneau, M., and Weingarten, D. 1985. The GFll supercomputer. In Proc., Symposium on Computer Architecture, pp. 108–114.
Boxer, L., and Miller, R. 1989. Parallel dynamic computational geometry. J. of New Generation Computer Systems, to appear.
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.
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.
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.
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.
Davenport, H., and Schinzel, A. 1965. A combinatorial problem connected with differential equations. Amer. J. Math., 87:684–694.
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.
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.
Duff, M.L.B., and Watson, D.M. 1977. The cellular logic array image processor. Computer J., 20:68–72.
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.
Hart, S., and Sharir, M. 1986. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica, 6:151–177.
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.
Hillis, D. 1985. The Connection Machine. MIT Press.
Intel Corp. 1986. iPSC System Overview (Jan.).
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.
Lempel, A., and Ziv, J. 1986. Compression of two-dimensional data. IEEE Trans. Information Theory, 32:2–8.
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.
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.
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.
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.
Miller, R., and Stout, Q.F. 1988b. Efficient parallel convex hull algorithms. IEEE Trans. on Computers, 37:1605–1618.
Miller, R., and Stout, Q.F. 1989a. Mesh computer algorithms for computational geometry. IEEE Trans. on Computers, 38:321–340.
Miller, R., and Stout, Q.F. 1989b. Parallel Algorithms for Regular Architectures. MIT Press, Cambridge, Mass., to appear.
Nassimi, D., and Sahni, S. 1980. Finding connected components and connected ones on a mesh-connected parallel computer. SIAM J. Comput., 9:744–757.
Potter, J.L., ed. 1985. The Massively Parallel Processor. MIT Press, Cambridge, Mass.
Preparata, F.P., and Lee, D.T. 1984. Computational geometry—A survey. IEEE Trans. on Computers, C-33:1072–1100.
Preparata, F.P., and Shamos, M.I. 1985. Computational Geometry. Springer-Verlag, New York.
Reddaway, S.F. 1978. DAP—A flexible number cruncher. In Proc., LASL Workshop on Vector Parallel Processors, pp. 233–234.
Reif, J.H., and Valiant, L.G. 1987. A logarithmic time sort for linear size networks. JACM, 34:60–76.
Reingold, E.M., Nievergelt, J., and Deo, N. 1977. Combinatorial Algorithms. Prentice Hall, New York.
Saad, Y., and Schultz, M.H. 1989. Data communication in hypercubes. J. of Parallel and Distributed Computing, 6, 1 (Feb.), 115–135.
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.
Shamos, M.I. 1975. Geometric complexity. In Proc., 7th Annual ACM Symposium on Theory of Computing, pp. 224–233.
Sharir, M. 1987. Almost linear upper bounds on the length of general Davenport-Schinzel sequences. Combinatorica, 7: 131–143.
Slotnick, D.L., Borck, W.C., and McReynolds, R.C. 1962. The SOLOMON computer. In Proc. AFIPS Fall Joint Comp. Conf., pp. 97–107.
Stout, Q.F. 1983. Topological matching. In Proc., 15th ACM Symposium on Theory of Computing, pp. 24–31.
Szemeredi, E. 1974. On a problem of Davenport and Schinzel. Acta Arith., 25: 213–224.
Thompson, C.D., and Kung, H.T. 1977. Sorting on a mesh-connected parallel computer. Communications of the ACM, 20:263–271.
Yaglom, I.M., and Boltyanskii, V.G. 1961. Convex Figures. Holt, Rinehart and Winston, New York.
Author information
Authors and Affiliations
Additional information
Research partially supported by a grant from the Niagara University Research Council.
Research partially supported by National Science Foundation grants DCR-8608640 and IRI-8800514.
Rights and permissions
About this article
Cite this article
Boxer, L., Miller, R. Dynamic computational geometry on meshes and hypercubes. J Supercomput 3, 161–191 (1989). https://doi.org/10.1007/BF00127827
Issue Date:
DOI: https://doi.org/10.1007/BF00127827