We propose a dynamic data structure for the distribution-sensitive point location problem in the plane. Suppose that there is a fixed query distribution within a convex subdivision S , and we are given an oracle that can return in O (1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain S such that each query is answered in O opt (S) ) expected time, where opt ( S ) is the expected time of the best linear decision tree for answering point location queries in S . The space and construction time are O(n log 2 n ), where n is the number of vertices of S . An update of S as a mixed sequence of k edge insertions and deletions takes O(k log 4 n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log 4 n ) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.

We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in ℝ², and we are given an oracle that can return in O(1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain a convex subdivision S with n vertices such that each query is answered in O(OPT) expected time, where OPT is the minimum expected time of the best linear decision tree for point location in S. The space and construction time are O(n log² n). An update of S as a mixed sequence of k edge insertions and deletions takes O(k log⁵ n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of n sites can be performed in O(n log⁵ n) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.

We present a self-adjusting point location structure for convex subdivisions. Let n be the number of vertices in a convex subdivision S. Our structure for S uses O(n) space and processes any online query sequence sigma in O(n + OPT) time, where OPT is the minimum time required by any linear decision tree for answering point location queries in S to process sigma. The O(n + OPT) time bound includes the preprocessing time. Our result is a two-dimensional analog of the static optimality property of splay trees. For connected subdivisions, we achieve a processing time of O(|sigma| log log n + n + OPT).

We present an algorithm for surface reconstruction from a point cloud. It runs in O ( n log n ) time, where n is the number of sample points, and this is optimal in the pointer machine model. The only existing O ( n log n )-time algorithm is due to Funke and Ramos, and it uses some sophisticated data structures. The key task is to extract a locally uniform subsample from the input points. Our algorithm is much simpler and it is based on a variant of the standard octree. We built a prototype that runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the sample points absent from the subsample via edge flips. In our experiments with some nonuniform samples, the subsample extraction step is fast and effective, and the prototype gives a 51% to 68% speedup over using Cocone alone. The prototype also runs faster on locally uniform samples.

We present an algorithm to reconstruct a surface from a dense sample. Given n sample points, it runs in O(n log n) time, which is optimal in the pointer machine model. The only existing O(n log n)-time algorithm due to Funke and Ramos uses some sophisticated data structures for the key task of extracting a locally uniform subsample. Our algorithm is based on a variant of the standard octree, and it is much simpler. We built a prototype, which runs an implementation of our algorithm to extract a locally uniform subsample, invokes Cocone to reconstruct a surface from the subsample, and adds back the samples points absent from the subsample via edge flips. The subsample extraction step is very fast and effective. In our experiments with some non-uniform samples, our prototype gives a 51% to 68% speedup from using Cocone alone. Even for locally uniform samples, our prototype is usually much faster.