Having been hacked too many times for parasitic SEO, I have decided that it’s time to upgrade our admittedly outdated wordpress installation. In the process, we lose quite a bit of functionality because of incompatibilies. Right now I am very short on time due to thesis writing and so I don’t know when I will be able to fix these problems. The one I really miss is the event calendar since I actually use it myself!
Frankly, I have considered “folding” completely since at this moment of my life I really don’t have the time, but then I figured that some of the existing content may be useful to others and so I decided to spend my time this way. Hope this is the right choice!
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)
