People and papers related to SVR

The following people have worked on SVR:

• Umut A. Acar
• Benoît Hudson
• Gary L. Miller
• Todd Phillips

List of publications

• Dynamic Mesh Refinement (pdf ps.gz bib) Benoît Hudson. Carnegie Mellon University Ph.D. thesis CMU-CS-07-162, 2007.

  Chapters 2 and 3 expand the results from the SVR implementation. The thesis also describes a dynamic meshing algorithm, not yet implemented. See also the talk (Keynote pdf).

• SVR: Practical Engineering for a Fast 3D Meshing Algorithm. Umut A. Acar, Benoît Hudson, Gary L. Miller, and Todd Phillips. 16th International Meshing Roundtable, 2007. (pdf bib)

  Describes the implementation of SVR, as of version 0.1. See also the talk (Keynote).

• Sparse Parallel Delaunay Mesh Refinement. Benoît Hudson, Gary Miller, and Todd Phillips. Symposium on Parallelism in Algorithms and Architectures, 2007. (pdf ps bib)

  SVR, in parallel. We get essentially O(log² m) parallel depth and optimal O(n log n + m) work bounds for meshing PLC input in any fixed dimension. We produce good aspect-ratio meshes rather than merely good radius-edge meshes by using the Li-Teng technique, which we show how to parallelize. This is not yet implemented.

• Optimal-time dynamic mesh refinement: preliminary results. Umut A. Acar, Benoît Hudson. Fall workshop on Computational Geometry, 2006. (pdf bib)

  Umut A. Acar and I presented our preliminary work on dynamizing SVR. Experimentally, we get approximately O(polylog n) performance. Errata: the curve fit to the data is 12.5 n lg^3(n). What's a constant factor between friends? Nota bene: Hudson 07 indicates that this cannot be done in the worst case, and provides a different meshing algorithm.

• Sparse Voronoi Refinement. Benoît Hudson, Gary Miller, and Todd Phillips. 15th International Meshing Roundtable, 2006. (pdf ps bib).

  This is the theoretical paper that spawned the SVR implementation. We describe how to perform Delaunay mesh refinement in any fixed dimension, producing a quality radius-edge mesh that is within a constant factor of optimal in size, and does so in optimal time on a broad class of inputs. In two dimensions, we match two prior results. In three and higher dimensions, we have the first subquadratic runtimes. See also the technical report CMU-CS-06-132 for a longer version with full algorithms and proofs.