INHERENTLY PARALLEL GEOMETRIC COMPUTATIONS
Abstract
A new computational paradigm is described which offers the possibility of superlinear (and sometimes unbounded) speedup, when parallel computation is used. The computations involved are subject only to given mathematical constraints and hence do not depend on external circumstances to achieve superlinear performance. The focus here is on geometric transformations. Given a geometric object A with some property, it is required to transform A into another object B which enjoys the same property. If the transformation requires several steps, each resulting in an intermediate object, then each of these intermediate objects must also obey the same property. We show that in transforming one triangulation of a polygon into another, a parallel algorithm achieves a superlinear speedup. In the case where a convex decomposition of a set of points is to be transformed, the improvement in performance is unbounded, meaning that a parallel algorithm succeeds in solving the problem as posed, while all sequential algorithms fail.
This research was supported by the Natural Sciences and Engineering Research Council of Canada.
References
- Computational Geometry: Theory and Applications 21(1–2), 3 (2002). Crossref, ISI, Google Scholar
-
O. Aichholzer and K. Reinhardt , A quadratic distance bound on sliding between crossing-free spanning trees , Proceedings of the Twentieth European Workshop on Computational Geometry . Google Scholar -
S. G. Akl , Parallel Computation: Models And Methods ( Prentice Hall , Upper Saddle River, New Jersey , 1997 ) . Google Scholar - Parallel and Distributed Computing Practices 4(3), 301 (2001). Google Scholar
- Computing and Informatics 21(5), 455 (2002). ISI, Google Scholar
- Parallel and Distributed Computing Practices 5(2), 193 (2003). ISI, Google Scholar
- Parallel Processing Letters 13(1), 65 (2003). Link, ISI, Google Scholar
- The Journal of Supercomputing 29, 89 (2004), DOI: 10.1023/B:SUPE.0000022574.59906.20. Crossref, ISI, Google Scholar
- , Parallel Numerics,
Systems and Simulation , eds.R. Trobec (University of Salzburg, Austria and Jožef Stefan Institute, Ljubljana, Slovenia, 2005) pp. 211–236. Google Scholar - S. G. Akl, Coping with uncertainty and stress: A parallel computation approach, to appear in International Journal of High Performance Computing and Networking . Google Scholar
- Parallel Processing Letters 9(4), 499 (1999), DOI: 10.1142/S0129626499000463. Link, Google Scholar
- International Journal of Computers and their Applications 7(1), 31 (2000). ISI, Google Scholar
- The Journal of Supercomputing 19(2), 219 (2001), DOI: 10.1023/A:1011179823237. ISI, Google Scholar
- International Journal of Parallel, Emergent and Distributed systems 20(2), 147 (2005), DOI: 10.1080/17445760500033432. Crossref, ISI, Google Scholar
S. G. Akl and W. Yao , Parallel computation applied to dynamical systems, Proceedings of the Seventeenth International Conference on Parallel and Distributed Computing Systems pp. 13–20. Google Scholar- Journal of Mathematical Modelling and Algorithms 4, 5 (2005), DOI: 10.1007/s10852-004-3519-x. Crossref, Google Scholar
- Algorithmica 16, 618 (1996). Crossref, ISI, Google Scholar
- Discrete Applied Mathematics 65, 21 (1996), DOI: 10.1016/0166-218X(95)00026-N. Crossref, ISI, Google Scholar
- Operations Research 42, 65 (1994), DOI: 10.1287/opre.42.1.65. Crossref, ISI, Google Scholar
-
A. Bestavros and V. Fay-Wolfe (eds.) , Real-Time Database and Information Systems ( Kluwer Academic Publishers , Boston , 1997 ) . Google Scholar - S. D. Bruda, Parallel Real-Time Complexity Theory, Ph.D. thesis, Department of Computing and Information Science, Queen's University, Kingston, Ontario, April 2002 . Google Scholar
- Theory of Computing Systems 33, 85 (2000), DOI: 10.1007/s002249910005. Crossref, ISI, Google Scholar
- Theory of Computing Systems 34(6), 565 (2001). Crossref, ISI, Google Scholar
- Parallel Processing Letters 11(2 & 3), 353 (2001), DOI: 10.1016/S0129-6264(01)00064-6. Link, ISI, Google Scholar
- Journal of Parallel and Distributed Computing 61(5), 688 (2001), DOI: 10.1006/jpdc.2000.1707. Crossref, ISI, Google Scholar
S. D. Bruda and S. G. Akl , On the relation between parallel real-time computations and logarithmic space, Proceedings of the Fourteenth Conference on Parallel and Distributed Computing and Systems pp. 102–107. Google Scholar- Information Processing Letters 86(4), 221 (2003), DOI: 10.1016/S0020-0190(02)00499-4. Crossref, ISI, Google Scholar
- International Journal of Computers and Applications 25(4), 247 (2003). Crossref, ISI, Google Scholar
D. Clark and M. Bailey , Visualization of height field data with physical models and texture photomapping, Proceedings of the IEEE Visualization'97 Conference pp. 89–94. Google Scholar-
T H. Cormen , Introduction to Algorithms ( McGraw-Hill , New York , 2001 ) . Google Scholar P. Desnoguès and O. Devilliers , A locally optimal triangulation of the hyperbolic paraboloid, Proceedings of the Seventh Canadian Conference on Computational Geometry pp. 49–54. Google Scholar- Algorithmica 15, 223 (1996), DOI: 10.1007/BF01975867. Crossref, ISI, Google Scholar
- , Computing in Euclidean Geometry, 2nd edn., eds.
D. Z. Du and F. K. Hwang (World Scientific Publishing, Singapore, 1995) pp. 225–265. Link, Google Scholar - International Journal of Computational Geometry and Applications 13(2), 113 (2003). Link, ISI, Google Scholar
-
P. L. George and H. Borouchaki , Triangulation de Delaunay et Maillage – Applications Aux Éléments Finis ( Hermes Science Publishing , London, England , 1997 ) . Google Scholar - Parallel Computing 29, 663 (2003), DOI: 10.1016/S0167-8191(03)00048-6. Crossref, ISI, Google Scholar
- Communications of the ACM 31, 532 (1988), DOI: 10.1145/42411.42415. Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 1, 250 (1990), DOI: 10.1109/71.80148. Crossref, Google Scholar
- Computer Graphics 30, 99 (1996). Google Scholar
- Computer Graphics 33, 269 (1999). Google Scholar
- Computational Geometry: Theory and Applications 13(3), 179 (1999). Crossref, ISI, Google Scholar
- Discrete and Computational Geometry 22, 333 (1999). Crossref, ISI, Google Scholar
- K. Islam, H. Meijer, and S. G. Akl, On the complexity of certain geometric transformations, manuscript in preparation, School of Computing, Queen's University, 2004 . Google Scholar
- Parallel Computing 4, 211 (1987). Crossref, ISI, Google Scholar
- Computer Aided Geometric Design 8, 419 (1991), DOI: 10.1016/0167-8396(91)90038-D. Google Scholar
I. Kolingerova and J. Kohout , Pessimistic threaded Delaunay triangulation by randomized incremental insertion, Proceedings of the International Conference on Computer Graphics and Vision (GraphiCon'2000) pp. 76–83. Google ScholarJ. Kohout , Parallel incremental Delaunay triangulation, Proceedings of the Fifth Central European Seminar on Computer Graphics pp. 85–94. Google Scholar-
C. M. Krishna and K. G. Shin , Real-Time Systems ( Mc-Graw Hill , New York , 1997 ) . Google Scholar - Communications of the ACM 27, 594 (1984), DOI: 10.1145/358080.358103. Crossref, ISI, Google Scholar
- , Mathematical Software III, ed.
J. Rice (Academic Press, New York, 1977) pp. 161–194. Crossref, Google Scholar -
H. W. Lawson , Parallel Processing in Industrial Real-Time Applications ( Prentice Hall , Englewood Cliffs, New Jersey , 1992 ) . Google Scholar - Journal of Algorithms 9, 503 (1988). Google Scholar
R. Mehrotra and E. F. Gehringer , Superlinear speedup through randomized algorithms, Proceedings of the International Conference on Parallel Processing pp. 291–300. Google Scholar- H. Meijer and D. Rappaport, Simultaneous edge flips for convex subdivisions, manuscript in preparation, School of Computing, Queen's University, 2004 . Google Scholar
M. Nagy and S. G. Akl , Real-time minimum vertex cover for two-terminal series-parallel graphs, Proceedings of the Thirteenth Conference on Parallel and Distributed Computing and Systems pp. 526–534. Google ScholarM. Nagy and S. G. Akl , Locating the median of a tree in real time, Proceedings of the Fourteenth Conference on Parallel and Distributed Computing and Systems pp. 108–113. Google ScholarM. Nagy and S. G. Akl , Computing nearest neighbors in real time, Proceedings of the Fifteenth Conference on Parallel and Distributed Computing and Systems pp. 518–524. Google Scholar- Parallel Computing 29(6), 767 (2003), DOI: 10.1016/S0167-8191(03)00022-X. Crossref, ISI, Google Scholar
- Parallel Computing 3, 261 (1986), DOI: 10.1016/0167-8191(86)90025-6. Crossref, ISI, Google Scholar
- Discrete and Computational Geometry 16(4), 419 (1996). Crossref, ISI, Google Scholar
W. J. Schroeder , A topology modifying progressive decimation algorithm, Proceedings of the IEEE Visualization'97 Conference pp. 205–213. Google Scholar- Journal of the American Mathematical Society 1, 647 (1988), DOI: 10.1090/S0894-0347-1988-0928904-4. Crossref, Google Scholar
- A. J. Stewart, Constructing long triangular strips using tunneling and mesh transformations, manuscript, School of Computing, Queen's University, 2004 . Google Scholar
-
M. Thorin , Real-Time Transaction Processing ( Macmillan, London , 1992 ) . Crossref, Google Scholar - Parallel Computing 30, 57 (2004), DOI: 10.1016/j.parco.2002.07.001. Crossref, ISI, Google Scholar
- AI Magazine 73 (1996). Google Scholar


