Reconstruction of Surfaces with Sharp Features
Given only an unorganized cloud of points sampled from a surface, recover the surface, including its corners and creases. The relative neighborhood graph of the samples is built, its small cycles are read off as faces, and under mild sampling conditions the result is homeomorphic to the original, even where it is not smooth.
Fast and Space-Efficient Top-k Queries on Time Series
Which of ten thousand series are the largest at a given instant? The ranking only changes where two series cross, so store the crossings rather than the rankings. The resulting index is orders of magnitude smaller than earlier approaches and answers queries with an asymptotically optimal number of I/O operations.
k-Clustering Queries and Embeddings of Road Networks
Shortest-path distance on a road network can be embedded in Euclidean space with bounded distortion. Once it is, k-means, k-medians, and k-centers queries over the network reduce to fast nearest-neighbor search, giving constant-factor approximations that run interactively on city-scale data.
Correlated Monte Carlo for the Linearized Poisson-Boltzmann Equation
The electrostatics of a molecule in salt water are governed by the Poisson-Boltzmann equation. Random walks on spheres solve it without a mesh, and reusing the same walks across salt concentrations correlates the estimates, so the whole concentration range is obtained from one Monte Carlo run.