Two New Results in Computational Geometry

Don Sheehy, CMU

August 8, 2008, 3:30PM, Wean 7220

Abstract:

In the meshing problem, we decompose a geometric domain into as few simplices as possible while ensuring each simplex achieves some quality (roundness) guarantee. For years, a proof of “size optimality” has been the most important stamp of approval needed by any new meshing algorithm, where size is measured as the number of simplices in the output. However, the lower bound used for these optimality proofs is not in general bounded by any function of the input size. This leads us to think that perhaps “size optimality” should not be the last word in mesh size analysis. In the first part of this talk, I will introduce well-paced point sets and prove that for this general class of inputs, standard meshing technology will produce linear size output. I will then show how to use this result to construct linear-size Delaunay meshes in any dimension by giving up quality guarantees exactly where the traditional size lower bound would dictate superlinear output.

In the second half of this double feature, I will change gears and present a data structure for Approximate Nearest Neighbor (ANN) search that achieves spatial adaptivity. That is, the algorithm can find constant-approximations to the nearest neighbor in log(d(p,q)) time per query, where q is the query point, p is the answer to the previous query, and d(p,q) is the number of points in a reasonably sized box containing p and q. Thus, we get worst-case O(log n)-time queries, but if the queries are spatially correlated, we can do even better. This is the first data structure to achieve spatial adaptivity for ANN.

(both results to appear at CCCG 2008)