We propose a dynamic data structure for the distribution-sensitive point location problem. Suppose that there is a fixed query distribution in $mathbb{R}^2$, and we are given an oracle that can return in $O(1)$ time the probability of a query point f
alling into a polygonal region of constant complexity. We can maintain a convex subdivision $cal S$ with $n$ vertices such that each query is answered in $O(mathrm{OPT})$ expected time, where OPT is the minimum expected time of the best linear decision tree for point location in $cal S$. The space and construction time are $O(nlog^2 n)$. An update of $cal S$ as a mixed sequence of $k$ edge insertions and deletions takes $O(klog^5 n)$ amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of $n$ sites can be performed in $O(nlog^5 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 self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let $n$ be the number of vertices in a convex or connected subdivision. Our structures use $O(n)$ space. For any convex subdivision $
S$, our method processes any online query sequence $sigma$ in $O(mathrm{OPT} + n)$ time, where $mathrm{OPT}$ is the minimum time required by any linear decision tree for answering point location queries in $S$ to process $sigma$. For connected subdivisions, the processing time is $O(mathrm{OPT} + n + |sigma|log(log^* n))$. In both cases, the time bound includes the $O(n)$ preprocessing time.
Surface reconstruction from an unorganized point cloud is an important problem due to its widespread applications. White noise, possibly clustered outliers, and noisy perturbation may be generated when a point cloud is sampled from a surface. Most ex
isting methods handle limited amount of noise. We develop a method to denoise a point cloud so that the users can run their surface reconstruction codes or perform other analyses afterwards. Our experiments demonstrate that our method is computationally efficient and it has significantly better noise handling ability than several existing surface reconstruction codes.
