February 12, 2008
Todd Phillips
10:00 AM, 4623 Wean Hall
Thesis Proposal
Title: Optimal Meshing Algorithms
Abstract:
The meshing problem is to decompose a geometric domain into simple elements that preserve the domain boundary. Meshing algorithms have been used for physical simulation and graphics applications for fifty years, but have only received serious theoretical attention in the last two decades. I propose to address two fundamental algorithmic questions in this area.
Many meshing algorithms require the use of a bounding box to mesh a larger region that contains the domain of interest. The extra elements are then discarded, similar to scaffolding around a construction project. I will provide a new output analysis of such meshing algorithms, where I will show that the number of extraneous scaffold elements is bounded by the number of interesting domain elements. This favorable result ensures that the output-sensitive runtime of such algorithms will depend only on the size of the domain mesh. This same framework shows that a 3D domain volume mesh is asymptotically the same size as a 2D boundary surface mesh, which has deep ramifications for the development of surface reconstruction and surface meshing algorithms.
An important characteristic of a domain to be meshed is the spread ($\Delta$), the ratio of the largest to smallest input feature. I propose the first runtime-optimal meshing algorithm that does not depend on $\Delta$. Previous optimal meshing algorithms work only for inputs with a constant $\log \Delta$ or a constant $\log\log \Delta$ (equivalent to fixed-length integer or floating-point models). Essential to the algorithm is a new eager point-location strategy. Novel low-entropy sorting techniques are developed for bucketing uninserted points. The algorithm also relies on centervertices, a new geometric construction related to centerpoints.
My research will also address related open questions on size-optimality for meshing algorithms.
Thesis Committee:
Gary L. Miller, Chair
Anupam Gupta
Daniel Sleator
Noel Walkington
Tamal Dey, Computer Science and Engineering, Ohio State
