No Access

INHERENTLY PARALLEL GEOMETRIC COMPUTATIONS

School of Computing, Queen's University, Kingston, Ontario, K7L 3N6, Canada

https://doi.org/10.1142/S0129626406002447Cited by:3 (Source: Crossref)

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.

Keywords:

References

O. Aichholzer, F. Aurenhammer and F. Hurtado, Computational Geometry: Theory and Applications 21(1–2), 3 (2002). Crossref, Web of Science, 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
S. G. Akl, Parallel and Distributed Computing Practices 4(3), 301 (2001). Google Scholar
S. G. Akl, Computing and Informatics 21(5), 455 (2002). Web of Science, Google Scholar
S. G. Akl, Parallel and Distributed Computing Practices 5(2), 193 (2003). Web of Science, Google Scholar
S. G. Akl, Parallel Processing Letters 13(1), 65 (2003). Link, Web of Science, Google Scholar
S. G. Akl, The Journal of Supercomputing 29, 89 (2004), DOI: 10.1023/B:SUPE.0000022574.59906.20. Crossref, Web of Science, Google Scholar
S. G. Akl, Parallel Numerics, Systems and Simulation, eds. R. Trobecet al. (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
S. G. Akl and S. D. Bruda, Parallel Processing Letters 9(4), 499 (1999), DOI: 10.1142/S0129626499000463. Link, Google Scholar
S. G. Akl and S. D. Bruda, International Journal of Computers and their Applications 7(1), 31 (2000). Web of Science, Google Scholar
S. G. Akl and S. D. Bruda, The Journal of Supercomputing 19(2), 219 (2001), DOI: 10.1023/A:1011179823237. Web of Science, Google Scholar
S. G. Akl, B. Cordy and W. Yao, International Journal of Parallel, Emergent and Distributed systems 20(2), 147 (2005), DOI: 10.1080/17445760500033432. Crossref, Web of Science, 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
S. G. Akl and W. Yao, Journal of Mathematical Modelling and Algorithms 4, 5 (2005), DOI: 10.1007/s10852-004-3519-x. Crossref, Google Scholar
D. Avis, Algorithmica 16, 618 (1996). Crossref, Web of Science, Google Scholar
D. Avis and K. Fukuda, Discrete Applied Mathematics 65, 21 (1996), DOI: 10.1016/0166-218X(95)00026-N. Crossref, Web of Science, Google Scholar
R. S. Barr and B. L. Hickman, Operations Research 42, 65 (1994), DOI: 10.1287/opre.42.1.65. Crossref, Web of Science, 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
S. D. Bruda and S. G. Akl, Theory of Computing Systems 33, 85 (2000), DOI: 10.1007/s002249910005. Crossref, Web of Science, Google Scholar
S. D. Bruda and S. G. Akl, Theory of Computing Systems 34(6), 565 (2001). Crossref, Web of Science, Google Scholar
S. D. Bruda and S. G. Akl, Parallel Processing Letters 11(2 & 3), 353 (2001), DOI: 10.1016/S0129-6264(01)00064-6. Link, Web of Science, Google Scholar
S. D. Bruda and S. G. Akl, Journal of Parallel and Distributed Computing 61(5), 688 (2001), DOI: 10.1006/jpdc.2000.1707. Crossref, Web of Science, 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
S. D. Bruda and S. G. Akl, Information Processing Letters 86(4), 221 (2003), DOI: 10.1016/S0020-0190(02)00499-4. Crossref, Web of Science, Google Scholar
S. D. Bruda and S. G. Akl, International Journal of Computers and Applications 25(4), 247 (2003). Crossref, Web of Science, 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 et al. , 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
H. Edelsbrunner and N. R. Shah, Algorithmica 15, 223 (1996), DOI: 10.1007/BF01975867. Crossref, Web of Science, Google Scholar
S. Fortune, 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
J. Galtieret al., International Journal of Computational Geometry and Applications 13(2), 113 (2003). Link, Web of Science, 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
F. Guerriero and M. Mancini, Parallel Computing 29, 663 (2003), DOI: 10.1016/S0167-8191(03)00048-6. Crossref, Web of Science, Google Scholar
J. L. Gustafson, Communications of the ACM 31, 532 (1988), DOI: 10.1145/42411.42415. Crossref, Web of Science, Google Scholar
D. P. Helmbold and C. E. McDowell, IEEE Transactions on Parallel and Distributed Systems 1, 250 (1990), DOI: 10.1109/71.80148. Crossref, Google Scholar
H. Hoppe, Computer Graphics 30, 99 (1996). Google Scholar
H. Hoppe, Computer Graphics 33, 269 (1999). Google Scholar
F. Hurtado and M. Noy, Computational Geometry: Theory and Applications 13(3), 179 (1999). Crossref, Web of Science, Google Scholar
F. Hurtado, M. Noy and J. Urrutia, Discrete and Computational Geometry 22, 333 (1999). Crossref, Web of Science, 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
R. Janssen, Parallel Computing 4, 211 (1987). Crossref, Web of Science, Google Scholar
B. Joe, 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 Scholar
J. 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
T. H. Lai and S. Sahni, Communications of the ACM 27, 594 (1984), DOI: 10.1145/358080.358103. Crossref, Web of Science, Google Scholar
C. L. Lawson, 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
J. Lucas, 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 Scholar
M. 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 Scholar
M. 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
N. Nagy and S. G. Akl, Parallel Computing 29(6), 767 (2003), DOI: 10.1016/S0167-8191(03)00022-X. Crossref, Web of Science, Google Scholar
D. Parkinson, Parallel Computing 3, 261 (1986), DOI: 10.1016/0167-8191(86)90025-6. Crossref, Web of Science, Google Scholar
M. Pocchiola and G. Vegter, Discrete and Computational Geometry 16(4), 419 (1996). Crossref, Web of Science, Google Scholar
W. J. Schroeder, A topology modifying progressive decimation algorithm, Proceedings of the IEEE Visualization'97 Conference pp. 205–213. Google Scholar
D. D. Sleator, R. E. Tarjan and W. P. Thurston, 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
M. Toulouse, T. G. Crainic and B. Sansó, Parallel Computing 30, 57 (2004), DOI: 10.1016/j.parco.2002.07.001. Crossref, Web of Science, Google Scholar
S. Zilberstein, AI Magazine 73 (1996). Google Scholar