CPS296.2: Advanced Topics in Computer Science
Mesh generation finds numerous applications in scientific computing, computer graphics, solid modeling, computer aided design, geographic information system, and medical imaging. In modeling the problems in these applications, the domains are partitioned into meshes consisting of small and simple elements (e.g. triangles, quadrilaterals, tetrahedra and hexahedra). Design and analysis of unstructured mesh generation algorithms will be the main theme in this course.
|Aug 26 M||Syllabus, course structure, etc.||HW#0 out [ps, pdf]|
|Aug 28 W||Triangulations and convex hulls [BKOS00, Chapter 1 & 11]: definitions; plane sweep algorithms; point set triangulations; amortized analysis; orientation test|
|Sep 2 M||Triangulations and convex hulls: Jarvis' march [J73]; Graham's scan [G72, A79], Chan's algorithm [C96]; polygon triangulations, size complexity, existence, finding diagonals, a recursive algorithm||HW#1 out [ps, pdf]|
|Sep 4 W||Polygon triangulations[BKOS00, Chapter 3]: triangulating monotone polygons; partitioning simple polygons into monotone polygons; coloring a triangulation; dual of a triangulation|
|Sep 9 M||Planar straight line graphs[E01, Chapter 2;
BKOS00, Chapter 3]:
definitions, triangulations, algorithm|
Voronoi diagrams and Delaunay triangulations [E01, Chapter 1; BKOS00, Chapters 7 & 9]: definitions, duality, empty-circle property, embedding
|Sep 11 W||Delaunay triangulation algorithm [E01, Chapter 1]: edge-flip, algorithm, local Delaunay condition, lifting to paraboloid, incircle test, termination, flip-connectivity, max-min angle property, worst-case construction||Graded HW#1 out|
|Sep 16 M||Int. Meshing Roundtable, Ithaca NY(no class)||HW#2 out [ps, pdf]|
|Sep 18 W|
|Sep 23 M||Randomized incremental DT algorithm [E01, Chapter 1; BKOS00, Chapter 9]: open problem: flip graph in 3D; incremental algorithm, proof of correctness, randomized analysis, point location[MSZ99], history DAG, searching time|
|Sep 25 W||Data Structures
quad-edge structure, triangle-based structure, comparison|
Element quality measures[TW00] smallest angle, largest angle, aspect ratio, radius-edge ratio, equivalence
Constrained/conforming Delaunay triangulations[E01]
|Sep 30 M||Delaunay Refinement[E01]: algorithm; Chew's and Ruppert's versions; quality guarantee, packing argument, local feature size, size optimality||HW#3 out [ps, pdf]|
|Oct 2 W||This class is moved to Oct 18 Friday|
|Oct 7 M||3D Delaunay Refinement[E01]: Schönhardt's and Chazelle's polyhedra, Chew's and Schewchuk's algorithms, slivers||Graded HW#2 out|
|Oct 9 W||
min-max angle, min-max height, edge-insertion, anchor property;
min weight triangulation, min max area triangulation|
Quad-tree refinement[BE95]: splitting, balancing, warping;
Project proposal due
|Oct 14 M||Fall Break (no class)|
|Oct 16 W||Nonobtuse triangulations [BE95, BE92]: motivation; no large vs. no small angles; optimality of non-obtuse triangulations: max-min angle, min-max angle, max-min height; slab algorithm;||HW#0 due|
|Oct 18 F||Acute and nonobtuse triangulations [BE95,BMR95]: circle-packing algorithm; space-filling tetrahedra, almost regular triangulations, acute tilings, space, slab; quality of tilings, open problems||Graded HW#3 out|
|Oct 21 M||Cubical meshing: cubical complex; transforming a simplicial complex into a cubical complex through refinement/coarsening||HW#4 out [ps, pdf]|
|Oct 23 W||Quadrilateral and hexahedral meshing: existence; flipping cubical meshes [BEE02]; circle-packing [BE96]; heuristics: advancing front methods (paving, plastering), mapping, duality and whisker weaving;|
|Oct 28 M||Sphere packings [LTU99]: well-spaced point set, simulatenous refinement and coarsening, adaptive meshing;|
|Oct 30 W||Smoothing and optimization [ABE99]::
Laplacian smoothing; LP-type optimization;|
Sliver removal [E01, ELMSTTUW00]: orthosphere, weighted Delaunay, perturbation
|Nov 4 M||Parallel mesh generation [STU02] conflicts and independence, parallelizing Chew's algorithm, parallelizing Ruppert's algorithm, edge classes.|
|Nov 6 W||Space-time meshing [EGSU02]:|
|Nov 11 M||Terrain reconstruction by Till Brenner|
|Nov 13 W||Shelling by Hai Yu|
|Nov 18 M|| Software and 3D printer demo
by Vijay Natarajan (meet at the Algorithms lab)
|Nov 20 W||Conference travel ( no class)|
|Nov 25 M||Hierarchical unstructured mesh generator for discretization of solids|
by Tian Xiao
|Project report due|
|Nov 27 W||Hexahedron based mesh generation for quasi-3D objects
by Gang Zhao
- H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, England, 2001. [course textbook]
- M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000.
- M. Bern. Adaptive mesh generation. pp. 1-46 of Error Estimation and Adaptive Discretization Methods in Computational Fluid Dynamics, T. Barth and H. Deconinck (ed.), Springer-Verlag, Heidelberg, 2002.
- M. Bern and D. Eppstein. Mesh generation and optimal triangulation. pp. 47-123 of Computing in Euclidean Geometry (2nd ed.), D.-Z. Du and F. Hwang (eds.), World Scientific, 1995.
- M. Bern and P. Plassmann. Mesh generation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier Science, 1999.
- H. Edelsbrunner. Triangulations and meshes in computational geometry. Acta Numerica, (2000), 133-213.
- S.-H. Teng and C. W. Wong. Unstructured mesh generation: Theory, practice, and perspectives. Int. J. Computational Geometry & Applications, 10(3):227-266, Jun 2000
- N.Amenta, M. Bern and D. Eppstein. Optimal Point Placement for Mesh Smoothing. J. Algorithms 30:302-322, 1999
- A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters 9(5):216-219, 1979. [A left-to-right variant of Graham's scan]
- M. Bern and D. Eppstein. Polynomial-Size Nonobtuse Triangulation Of Polygons. Int. J. of Comp. Geom. & Appl., 2:241-255, 1992
- M. Bern and D. Eppstein. Quadrilateral Meshing by Circle Packing Int. J. of Comp. Geom. & Appl., 10(4):347-360, 1996
- M. Bern, D. Eppstein, and J. Erickson. Flipping cubical meshes. To appear in Engineering with Computers, 2002
- M. Bern, S. Mitchell, and J. Ruppert. Linear Size Nonobtuse Triangulation Of Polygons. Discrete & Computational Geometry,14:411-428, 1995
- T. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry 16:361-368, 1996.
- J. Erickson, D. Guoy, J. Sullivan, and A. Üngör. Building space-time meshes over arbitrary spatial domains. Proceedings of the 11th International Meshing Roundtable, 391-402, 2002.
- R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters 1:132-133, 1972.
- L. J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Transactions on Graphics 4(2): 74-123 (1985)
- R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters 2:18-21, 1973.
- E. P. Mücke, I. Saiass, B. Zhu. Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations. Computational Geometry 12(1-2):63-83, 1999.
- D. Spielman, S.-H. Teng, and A. Üngör. Parallel Delaunay Refinement: Algorithms and Analyses. Proceedings of the 11th International Meshing Roundtable, 205-217, 2002.
Download the syllabus in [ps, pdf].