We provide a kinetic data structure (KDS) to the planar kinetic mesh refinement problem, which concerns computation of meshes of continuously moving points. Our KDS computes the Delaunay triangulation of a size-optimal well-spaced superset of a set of moving points with algebraic trajectories of constant degree. Our KDS is compact, requiring linear space in the size of the output. It is local, using a point in O(log Delta) certificates. It is responsive, repairing itself in O(log Delta) time per event. It is efficient, processing O(n2 log3 Delta) events in the worst case; this is optimal up to a polylogarithmic factor. Also, our KDS is dynamic, responding to point insertions and deletions in O(log Delta) time. In our bounds Delta stands for the geometric spread, the ratio of the diameter to the closest pair distance. To the best of our knowledge, this is the first KDS for mesh refinement.

Parallel algorithms and dynamic algorithms possess an interesting duality property: compared to sequential algorithms, parallel algorithms improve run-time while preserving work, while dynamic algorithms improve work but typically offer no parallelism. Although they are often considered separately, parallel and dynamic algorithms employ similar design techniques. They both identify parts of the computation that are independent of each other. This suggests that dynamic algorithms could be parallelized to improve work efficiency while preserving fast parallel run-time.

In a well-spaced point set, when there is a bounding hypercube, the Voronoi cells all have bounded aspect ratio, i.e., the distance from the Voronoi site to the farthest point in the Voronoi cell divided by the distance to the nearest neighbor in the set is bounded by a small constant. Well-spaced point sets satisfy some important geometric properties and yield quality Voronoi or simplicial meshes that can be important in scientific computations. In this paper, we consider the dynamic well-spaced point sets problem, which requires computing the well-spaced superset of a dynamically changing input set, e.g., as input points are inserted or deleted. We present a dynamic algorithm that allows inserting/deleting points into/from the input in worst-case O(log Δ) time, where Δ is the geometric spread, a natural measure that is bounded by O(log n) when input points are represented by log-size words. We show that the runtime of the dynamic update algorithm is optimal in the worst case. Our algorithm generates size-optimal outputs: the resulting output sets are never more than a constant factor larger than the minimum size necessary. A preliminary implementation indicates that the algorithm is indeed fast in practice. To the best of our knowledge, this is the first time- and size-optimal dynamic algorithm for well-spaced point sets.

We apply ideas from mesh generation to improve the time and space complexities of computing the full persistent homological information associated with a point cloud P in Euclidean space ℜd. Classical approaches rely on the Cech, Rips, ±-complex, or witness complex filtrations of P, whose complexities scale up very badly with d. For instance, the ±-complex filtration incurs the n Ω(d) size of the Delaunay triangulation, where n is the size of P. The common alternative is to truncate the filtrations when the sizes of the complexes become prohibitive, possibly before discovering the most relevant topological features. In this paper we propose a new collection of filtrations, based on the Delaunay triangulation of a carefully-chosen superset of P, whose sizes are reduced to 2O(d2)n. Our filtrations interleave multiplicatively with the family of offsets of P, so that the persistence diagram of P can be approximated in 2O(d2)n3 time in theory, with a near-linear observed running time in practice. Thus, our approach remains tractable in medium dimensions, say 4 to 10.

Typical volume meshes in three dimensions are designed to conform to an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh may be uniformly spaced or highly graded, and may have fine resolution due to extrinsic mesh size concerns. When we desire that such a volume mesh have good aspect ratio, we require that some space-filling scaffold vertices be inserted off the surface. We analyze the number of scaffold vertices in a setting that encompasses many existing volume meshing algorithms. We show that under simple preconditions, the number of scaffold vertices will be linear in the number of surface vertices.

The authors recently introduced the technique of sparse mesh refinement to produce the first near-optimal sequential time bounds of O(n lg L/s+m) for inputs in any fixed dimension with piecewiselinear constraining (PLC) features. This paper extends that work to the parallel case, refining the same inputs in time O(lg(L/s) lgm) on an EREW PRAM while maintaining the work bound; in practice, this means we expect linear speedup for any practical number of processors. This is faster than the best previously known parallel Delaunay mesh refinement algorithms in two dimensions. It is the first technique with work bounds equal to the sequential case. In higher dimension, it is the first provably fast parallel technique for any kind of quality mesh refinement with PLC inputs. Furthermore, the algorithm's implementation is straightforward enough that it is likely to be extremely fast in practice.

Combinatorial auctions, where bidders can bid on bundles of items, are known to be desirable auction mechanisms for selling items that are complementary and/or substitutable. However, there are 2k --1 bundles, and each agent may need to bid on all of them to fully express its preferences. We address this by showing how them auctioneer can recommend to the agents incrementally which bundles to bid on so that they need to only place a small fraction of all possible bids. These algorithms impose a great computational burden on the auctioneer; we show how to speed them up dramatically. We also present an optimal elicitor, which is intractable but may be the basis for future algorithms. Finally, we introduce the notion of a universal revelation reducer, demonstrate a randomized one, and prove that no deterministic one exists.The full paper is available in draft form at http://www.cs.cmu.edu/ sandholm/using_value_queries.pdf.