World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

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

  • O. Aichholzer, F. Aurenhammer and F. Hurtado, Computational Geometry: Theory and Applications 21(1–2), 3 (2002). Crossref, ISIGoogle 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). ISIGoogle Scholar
  • S. G. Akl, Parallel and Distributed Computing Practices 5(2), 193 (2003). ISIGoogle Scholar
  • S. G. Akl, Parallel Processing Letters 13(1), 65 (2003). Link, ISIGoogle Scholar
  • S. G. Akl, The Journal of Supercomputing 29, 89 (2004), DOI: 10.1023/B:SUPE.0000022574.59906.20. Crossref, ISIGoogle 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. LinkGoogle Scholar
  • S. G. Akl and S. D. Bruda, International Journal of Computers and their Applications 7(1), 31 (2000). ISIGoogle Scholar
  • S. G. Akl and S. D. Bruda, The Journal of Supercomputing 19(2), 219 (2001), DOI: 10.1023/A:1011179823237. ISIGoogle 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, ISIGoogle 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. CrossrefGoogle Scholar
  • D. Avis, Algorithmica 16, 618 (1996). Crossref, ISIGoogle Scholar
  • D. Avis and K. Fukuda, Discrete Applied Mathematics 65, 21 (1996), DOI: 10.1016/0166-218X(95)00026-N. Crossref, ISIGoogle Scholar
  • R. S. Barr and B. L. Hickman, Operations Research 42, 65 (1994), DOI: 10.1287/opre.42.1.65. Crossref, ISIGoogle 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, ISIGoogle Scholar
  • S. D. Bruda and S. G. Akl, Theory of Computing Systems 34(6), 565 (2001). Crossref, ISIGoogle 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, ISIGoogle 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, ISIGoogle 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, ISIGoogle Scholar
  • S. D. Bruda and S. G. Akl, International Journal of Computers and Applications 25(4), 247 (2003). Crossref, ISIGoogle 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, ISIGoogle 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. LinkGoogle Scholar
  • J. Galtieret al., International Journal of Computational Geometry and Applications 13(2), 113 (2003). Link, ISIGoogle 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, ISIGoogle Scholar
  • J. L. Gustafson, Communications of the ACM 31, 532 (1988), DOI: 10.1145/42411.42415. Crossref, ISIGoogle Scholar
  • D. P. Helmbold and C. E. McDowell, IEEE Transactions on Parallel and Distributed Systems 1, 250 (1990), DOI: 10.1109/71.80148. CrossrefGoogle 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, ISIGoogle Scholar
  • F. Hurtado, M. Noy and J. Urrutia, Discrete and Computational Geometry 22, 333 (1999). Crossref, ISIGoogle 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, ISIGoogle 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, ISIGoogle Scholar
  • C. L. Lawson, Mathematical Software III, ed. J. Rice (Academic Press, New York, 1977) pp. 161–194. CrossrefGoogle 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, ISIGoogle Scholar
  • D. Parkinson, Parallel Computing 3, 261 (1986), DOI: 10.1016/0167-8191(86)90025-6. Crossref, ISIGoogle Scholar
  • M. Pocchiola and G. Vegter, Discrete and Computational Geometry 16(4), 419 (1996). Crossref, ISIGoogle 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. CrossrefGoogle 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 ) . CrossrefGoogle Scholar
  • M. Toulouse, T. G. Crainic and B. Sansó, Parallel Computing 30, 57 (2004), DOI: 10.1016/j.parco.2002.07.001. Crossref, ISIGoogle Scholar
  • S. Zilberstein, AI Magazine 73 (1996). Google Scholar