Sparse parallel Delaunay mesh refinement

ABSTRACT

The authors recently introduced the technique of sparse mesh refinement to produce the first near-optimal sequential time bounds of O(n lg L/s+m) for inputs in any fixed dimension with piecewiselinear constraining (PLC) features. This paper extends that work to the parallel case, refining the same inputs in time O(lg(L/s) lgm) on an EREW PRAM while maintaining the work bound; in practice, this means we expect linear speedup for any practical number of processors. This is faster than the best previously known parallel Delaunay mesh refinement algorithms in two dimensions. It is the first technique with work bounds equal to the sequential case. In higher dimension, it is the first provably fast parallel technique for any kind of quality mesh refinement with PLC inputs. Furthermore, the algorithm's implementation is straightforward enough that it is likely to be extremely fast in practice.

REFERENCES

• 1: U. A. Acar and B. Hudson. Optimal-time dynamic mesh refinement: preliminary results. In Proc. 16th Fall Workshop on Computational Geometry, 2006.
• 2: Christos D. Antonopoulos , Xiaoning Ding , Andrey Chernikov , Filip Blagojevic , Dimitrios S. Nikolopoulos , Nikos Chrisochoides, Multigrain parallel Delaunay Mesh generation: challenges and opportunities for multithreaded architectures, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088198]
• 3: Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
• 4: M. W. Bern, D. Eppstein, and S.-H. Teng. Parallel construction of quadtrees and quality triangulations. International Journal of Computational Geometry and Applications, 9(6):517--532, 1999.
• 5: Daniel K. Blandford , Guy E. Blelloch , Clemens Kadow, Engineering a compact parallel delaunay algorithm in 3D, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137900]
• 6: G. E. Blelloch, J. C. Hardwick, G. L. Miller, and D. Talmor. Design and Implementation of a Practical Parallel Delaunay Algorithm. Algorithmica, 24(3-4):243--269, Aug. 1999.
• 7: G. E. Blelloch, J. C. Hardwick, G. L. Miller, and D. Talmor. Design and Implementation of a Practical Parallel Delaunay Algorithm. Algorithmica, 24(3-4):243--269, Aug. 1999.
• 8: A. Chernikov and N. Chrisochoides. Generalized delaunay mesh refinement: From scalar to parallel. In 15th International Meshing Roundtable, pages 563--580, Birmingham, AL, Sept 2006.
• 9: L. Chew, N. Paul, and F. Sukup. Parallel constrained delaunay meshing, 1997.
• 10: L. Paul Chew, Guaranteed-quality Delaunay meshing in 3D (short version), Proceedings of the thirteenth annual symposium on Computational geometry, p.391-393, June 04-06, 1997, Nice, France [doi>10.1145/262839.263018]
• 11: N. Chrisochoides and D. Nave. Simultaneous mesh generation and partitioning for delaunay meshes, 1999.
• 12: Herbert Edelsbrunner , Xiang-Yang Li , Gary Miller , Andreas Stathopoulos , Dafna Talmor , Shang-Hua Teng , Alper Üngör , Noel Walkington, Smoothing and cleaning up slivers, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.273-277, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335338]
• 13: A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States [doi>10.1145/28395.28429]
• 14: Sariel Har-Peled , Alper Üngör, A time-optimal delaunay refinement algorithm in two dimensions, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064128]
• 15: B. Hudson, G. Miller, and T. Phillips. Sparse Voronoi Refinement. In Proceedings of the 15th International Meshing Roundtable, pages 339--356, Birmingham, Alabama, 2006. Long version available as Carnegie Mellon University Technical Report CMU-CS-06-132.
• 16: B. Hudson, G. Miller, and T. Phillips. Sparse Voronoi Refinement. Technical Report CMU-CS-06-132, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, June 2006.
• 17: Martin Isenburg , Yuanxin Liu , Jonathan Shewchuk , Jack Snoeyink, Streaming computation of Delaunay triangulations, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 18: Clemens Martin Joachim Kadow , Omar Ghattas, Parallel delaunay refinement mesh generation, Carnegie Mellon University, Pittsburgh, PA, 2004
• 19: M. Kulkarni, L. P. Chew, and K. Pingali. Using transactions in delaunay mesh generation. In Workshop on Transactional Memory Workloads, 2006.
• 20: François Labelle, Sliver removal by lattice refinement, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137907]
• 21: Xiang-Yang Li, Generating well-shaped d-dimensional Delaunay meshes, Theoretical Computer Science, v.296 n.1, p.145-165, 4 March 2003 [doi>10.1016/S0304-3975(02)00437-1]
• 22: Xiang-Yang Li , Shang-Hua Teng, Generating well-shaped Delaunay meshed in 3D, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 07-09, 2001, Washington, D.C., United States
• 23: G. L. Miller, S. E. Pav, and N. J. Walkington. When and why ruppert's algorithm works. In Proceedings, 12th International Meshing Roundtable, pages 91--102. Sandia National Laboratories, September 14-17 2003.
• 24: Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
• 25: Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, On the Radius-Edge Condition in the Control Volume Method, SIAM Journal on Numerical Analysis, v.36 n.6, p.1690-1708, Dec. 1999 [doi>10.1137/S0036142996311854]
• 26: Scott A. Mitchell , Stephen A. Vavasis, Quality mesh generation in three dimensions, Proceedings of the eighth annual symposium on Computational geometry, p.212-221, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142720]
• 27: D. Nave and N. Chrisochoides. Boundary refinement in delaunay mesh generation using arbitrarily ordered vertex insertion. In CCCG, pages 282--285, 2005.
• 28: Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains, Proceedings of the eighteenth annual symposium on Computational geometry, p.135-144, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513418]
• 29: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 30: M. Shephard, J. E. Flaherty, H. L. de Cougny, C. Ozturan, C. L. Bottasso, andM. Beall. Parallel automated adaptive procedures for unstructured meshes. Technical report, RPI, 1995. URL: http://www.scorec.rpi.edu/REPORTS/1995-11.pdf.
• 31: D. Spielman, S.-H. Teng, and A. Üngör. Parallel Delaunay refinement: Algorithms and analyses. In Proceedings, 11th International Meshing Roundtable, pages 205--218. Sandia National Laboratories, September 15-18 2002. http://www.arxiv.org/abs/cs.CG/0207063.
• 32: Daniel A. Spielman , Shang-Hua Teng , Alper Üngör, Time complexity of practical parallel steiner point insertion algorithms, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007953]
• 33: TIANKAI TU , DAVID R. O'HALLARON , OMAR GHATTAS, Scalable Parallel Octree Meshing for TeraScale Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.4, November 12-18, 2005 [doi>10.1109/SC.2005.61]
• 34: M. J. Turner, R. W. Clough, H. C. Martin, and L. P. Topp. Stiffness and deflection analysis of complex structures. J. Aeronaut. Sci., 23:805--824, 1956.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
computational geometry, mesh generation, shared-memory parallelism