Presented in this paper is a sweepline algorithm to compute the Voronoi diagram of a set of circles in a two-dimensional Euclidean space. The radii of the circles are non-negative and not necessarily equal. It is allowed that circles intersect each other, and a circle contains others. The proposed algorithm constructs the correct Voronoi diagram as a sweepline moves on the plane from top to bottom. While moving on the plane, the sweepline stops only at certain event points where the topology changes occur for the Voronoi diagram being constructed. The worst-case time complexity of the proposed algorithm is $O((n+m)log n)$, where $n$ is the number of input circles, and $m$ is the number of intersection points among circles. As $m$ can be $O(n^22)$, the presented algorithm is optimal with $O(n^2 log n) $ worst-case time complexity.

Parameterizations of manifolds are widely applied to the fields of numerical partial differential equations and computer graphics. To this end, in recent years several efficient and reliable numerical algorithms have been developed by different research groups for the computation of triangular and tetrahedral mesh parameterizations. However, it is still challenging when the topology of manifolds is nontrivial, e.g., the 3-manifold of a topological solid torus. In this paper, we propose a novel volumetric stretch energy minimization algorithm for volume-preserving parameterizations of toroidal polyhedra with a single boundary being mapped to a standard torus. In addition, the algorithm can also be used to compute the equiareal mapping between a genus-one closed surface and the standard torus. Numerical experiments indicate that the developed algorithm is effective and performs well on the bijectivity of the mapping. Applications on manifold registrations and partitions are demonstrated to show the robustness of our algorithms.

Detecting deformities on objects is a typical topic in shape analysis, and has much applications such as abnormalities detection in medical imaging (e.g. growth of tumor, spread of cancer). While many algorithms are already well-established in a 2-dimensional case when the object is indeed a surface, a model that still performs well in the general n-dimensional case is still missing. It is our goal in this paper to complete this missing piece, by introducing an indicator in order to effectively distinguish between normal and abnormal deformities. The proposed framework is closely related to the classic 2-dimensional conformal geometry and quasi-conformal geometry. In this work, we model abnormal deformations by anisotropic deformations. Given any two objects of the same dimension (with landmark constraints in between), we define the Anisotropic Indicator, a locally defined real-valued function on the original object, which demonstrates the abnormalities in the deformation between them. Both global and local features about the abnormalities between the two objects can be tracked by analyzing the indicator. We tested the algorithm by detecting deformations on synthetic data and real data, and results show that our algorithm can detect deformations of different types and degrees.

We address the problem of surface inpainting, which aims to fill in holes or missing regions on a Riemann surface based on its surface geometry. In practical situation, surfaces obtained from range scanners often have holes where the 3D models are incomplete. In order to analyze the 3D shapes effectively, restoring the incomplete shape by filling in the surface holes is necessary. In this paper, we propose a novel conformal approach to inpaint surface holes on a Riemann surface based on its surface geometry. The basic idea is to represent the Riemann surface using its conformal factor and mean curvature. According to Riemann surface theory, a Riemann surface can be uniquely determined by its conformal factor and mean curvature up to a rigid motion. Given a Riemann surface S, its mean curvature H and conformal factor λ can be computed easily through its conformal parameterization. Conversely, given λ and H, a Riemann surface can be uniquely reconstructed by solving the Gauss-Codazzi equation on the conformal parameter domain. Hence, the conformal factor and the mean curvature are two geometric quantities fully describing the surface. With this λ-H representation of the surface, the problem of surface inpainting can be reduced to the problem of image inpainting of λ and H on the conformal parameter domain. Once λ and H are inpainted, a Riemann surface can be reconstructed which effectively restores the 3D surface with missing holes. Since the inpainting model is based on the geometric quantities λ and H, the restored surface follows the surface geometric pattern. We test the proposed algorithm on synthetic data as well as real surface data. Experimental results show that our proposed method is an effective surface inpainting algorithm to fill in surface holes on an incomplete 3D models based their surface geometry.

This work proposes a novel framework for optimization in the constrained diffeomorphism space for deformable surface registration. First the diffeomorphism space is modeled as a special complex functional space on the source surface, the Beltrami coefficient space. The physically plausible constraints, in terms of feature landmarks and deformation types, define subspaces in the Beltrami coefficient space. Then the harmonic energy of the registration is minimized in the constrained subspaces. The minimization is achieved by alternating two steps: 1) optimization - diffuse the Beltrami coefficient, and 2) projection - first deform the conformal structure by the current Beltrami coefficient and then compose with a harmonic map from the deformed conformal structure to the target. The registration result is diffeomorphic, satisfies the physical landmark and deformation constraints, and minimizes the conformality distortion. Experiments on human facial surfaces demonstrate the efficiency and efficacy of the proposed registration framework.