We propose a new method to obtain landmark-matching transformations between n-dimensional Euclidean spaces with large deformations. Given a set of feature correspondences, our algorithm searches for an optimal folding-free mapping that satisfies the prescribed landmark constraints. The standard conformality distortion defined for mappings between 2-dimensional spaces is first generalized to the n-dimensional conformality distortion K(f) for a mapping f between n-dimensional Euclidean spaces (n≥3). We then propose a variational model involving K(f) to tackle the landmark-matching problem in higher dimensional spaces. The generalized conformality term K(f) enforces the bijectivity of the optimized mapping and minimizes its local geometric distortions even with large deformations. Another challenge is the high computational cost of the proposed model. To tackle this, we have also proposed a numerical method to solve the optimization problem more efficiently. Alternating direction method with multiplier (ADMM) is applied to split the optimization problem into two subproblems. Preconditioned conjugate gradient method with multi-grid preconditioner is applied to solve one of the sub-problems, while a fixed-point iteration is proposed to solve another subproblem. Experiments have been carried out on both synthetic examples and lung CT images to compute the diffeomorphic landmark-matching transformation with different landmark constraints. Results show the efficacy of our proposed model to obtain a folding-free landmark-matching transformation between n-dimensional spaces with large deformations.

Alzheimer's disease (AD) is a no-cure disease that has been frustrating the scientists for many years. Analyzing the disease has become an important but challenging research topic. The shape analysis of the sub-cortical structure of AD patients has been commonly used to understand this disease. In this paper, we assess the feasibility of using shape information on the hippocampal (HP) surfaces to detect some sub-structural changes in AD patients. We propose a quasi-conformal statistical shape analysis model, which allows us to study local regional geometric changes in the HPs amongst normal control (NC) and AD groups. A shape index defined by the quasi-conformality and surface curvatures is used to characterize region-specific shape variations of the HP surfaces. Feature vectors can be extracted for each HPs, with which a classification model can be built using machine learning methods to classify HPs into NC and AD subjects. Experiments have been carried out on 99 normal controls and 41 patients with AD. Results demonstrate that the proposed quasi-conformal based model is effective for classifying HPs into NC and AD groups with high classification accuracy (with highest overall classification accuracy reaching 87.86% in a leave-one-out experiment using the whole dataset).

Point cloud is the most fundamental representation of 3D geometric objects as it provides the most exact information of them. Analyzing and processing point cloud surfaces is important in computer graphics and computer vision. However, most of the existing algorithms for surface analysis require connectivity information. Therefore, it is desirable to develop a mesh structure on point clouds. This task can be simplified with the aid of a parameterization. In particular, conformal parameterizations are advantageous in preserving the geometric information of the point cloud data. In this paper, we extend a state-of-the-art spherical conformal parameterization algorithm for genus-0 closed meshes to the case of point clouds, using an improved approximation of the Laplace-Beltrami operator on data points. Then, we propose an iterative scheme called the North-South reiteration for achieving a spherical conformal parameterization. A balancing scheme is introduced to enhance the distribution of the spherical parameterization. High quality triangulations and quadrangulations can then be built on the point clouds with the aid of the parameterizations. Also, the meshes generated are guaranteed to be genus-0 closed meshes. Moreover, using our proposed spherical conformal parameterization, multilevel representations of point clouds can be easily constructed. Experimental results demonstrate the effectiveness of our proposed framework.

In this paper we show that stability for holomorphic vector bundles are equivalent to the existence of solutions to certain system of Monge Ampere equations parametrized by a parameter k. We solve this fully nonlinear elliptic system by singular perturbation technique and show that the vanishing of obstructions for the perturbation is given precisely by the stability condition. This can be interpreted as an infinite dimensional analog of the equivalencybetween Geometric Invariant Theory and Symplectic Reduction for moduli space of vector bundles.

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.

Surface parameterizations have been widely applied to digital geometry processing. In this paper, we propose an efficient conformal energy minimization (CEM) algorithm for computing conformal parameterizations of simply-connected open surfaces with a very small angular distortion and a highly improved computational efficiency. In addition, we generalize the proposed CEM algorithm to computing conformal parameterizations of multiply-connected surfaces. Furthermore, we prove the existence of a nontrivial accumulation point of the proposed CEM algorithm under some mild conditions. Several numerical results show the efficiency and robustness of the CEM algorithm comparing to the existing state-of-the-art algorithms. An application of the CEM on the surface morphing between simply-connected open surfaces is demonstrated thereafter. Thanks to the CEM algorithm, the whole computations for the surface morphing can be performed efficiently and robustly.

No abstract uploaded!

In this paper, we investigate how to topologically and geometrically characterize the intersection relations between a movable convex polygon and a set  of possibly overlapping polygons fixed in the plane. More specifically, a subset   is called an intersection relation if there exists a placement of that intersects, and only intersects, . The objective of this paper is to design an efficient algorithm that finds a finite and discrete representation of all of the intersection relations between and . Past related research only focuses on the complexity of the free space of the configuration space between and  and how to move or place an object in this free space. However, there are many applications that require the knowledge of not only the free space, but also the intersection relations. Examples are presented to demonstrate the rich applications of the formulated problem on intersection relations.

In this paper, we consider the problem of approximating the longest path in a grid graph that possesses a square-free 2-factor. By (1) analyzing several characteristics of four types of cross cells and (2) presenting three cycle-merging operations and one extension operation, we propose an algorithm that finds in an n-vertex grid graph G, a long path of length at least 5/6 n + 2. Our approximation algorithm runs in quadratic time. In addition to its theoretical value, our work has also an interesting application in image-guided maze generation.

In the research of computer vision and machine perception, 3D objects are usually represented by 2-manifold triangular meshes M. In this paper, we present practical and efficient algorithms to construct iso-contours, bisectors, and Voronoi diagrams of point sites onM, based on an exact geodesic metric. Compared to euclidean metric spaces, the Voronoi diagrams onMexhibit many special properties that fail all of the existing euclidean Voronoi algorithms. To provide practical algorithms for constructing geodesicmetric- based Voronoi diagrams onM, this paper studies the analytic structure of iso-contours, bisectors, and Voronoi diagrams onM. After a necessary preprocessing of model M, practical algorithms are proposed for quickly obtaining full information about iso-contours, bisectors, and Voronoi diagrams on M. The complexity of the construction algorithms is also analyzed. Finally, three interesting applications—surface sampling and reconstruction, 3D skeleton extraction, and point pattern analysis—are presented that show the potential power of the proposed algorithms in pattern analysis.

We study the combinatorial complexity of Voronoi diagram of point sites on a general triangulated 2-manifold surface, based on the geodesic metric. Given a triangulated 2- manifold T of n faces and a set of m point sites S = {s1, s2, . . . , sm} ∈ T, we prove that the complexity of Voronoi diagram VT (S) of S on T is O(mn) if the genus of T is zero. For a genus-g manifold T in which the samples in S are dense enough and the resulting Voronoi diagram satisfies the closed ball property, we prove that the complexity of Voronoi diagram VT (S) is O((m + g)n).

A natural metric in 2-manifold surfaces is to use geodesic distance. If a 2-manifold surface is represented by a triangle mesh T , the geodesic metric on T can be computed exactly using computational geometry methods. Previous work for establishing the geodesic metric on T only supports using half-edge data structures; i.e., each edge e in T is split into two halves (he1, he2) and each half-edge corresponds to one of two faces incident to e. In this paper, we prove that the exact-geodesic structures on two halfedges of e can be merged into one structure associated with e. Four merits are achieved based on the properties which are studied in this paper: (1) Existing CAD systems that use edge-based data structures can directly add the geodesic distance function without changing the kernel to a half-edge data structure; (2) To find the geodesic path from inquiry points to the source, the MMP algorithm can be run in an onthe- fly fashion such that the inquiry points are covered by correct wedges; (3) The MMP algorithm is sped up by pruning unnecessary wedges during the wedge propagation process; (4) The storage of the MMP algorithm is reduced since fewer wedges need to be stored in an edge-based data structure. Experimental results show that when compared to the classic half-edge data structure, the edge-based implementation of the MMP algorithm reduces running time by 44% and storage by 29% on average.

This paper studies the Voronoi diagrams on 2-manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point-source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line-segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n-face mesh with m generators, where N = max{m,n}. Computational results on real-world models demonstrate the efficiency of our algorithm.

Centroidal Voronoi tessellation (CVT) is a special type of Voronoi diagram such that the generating point of each Voronoi cell is also its center of mass. The CVT has broad applications in computer graphics, such as meshing, stippling, sampling, etc. The existing methods for computing CVTs on meshes either require a global parameterization or compute it in the restricted sense (that is, intersecting a 3D CVT with the surface). Therefore, these approaches often fail on models with complicated geometry and/or topology. This paper presents two intrinsic algorithms for computing CVT on triangle meshes. The first algorithm adopts the Lloyd framework, which iteratively moves the generator of each geodesic Voronoi diagram to its mass center. Based on the discrete exponential map, our method can efficiently compute the Riemannian center and the center of mass for any geodesic Voronoi diagram. The second algorithm uses the L-BFGS method to accelerate the intrinsic CVT computation. Thanks to the intrinsic feature, our methods are independent of the embedding space, and work well for models with arbitrary topology and complicated geometry, where the existing extrinsic approaches often fail. The promising experimental results show the advantages of our method.

Computing geodesic distances on triangle meshes is a fundamental problem in computational geometry and computer graphics. To date, two notable classes of algorithms, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been proposed. Although these algorithms can compute exact geodesic distances if numerical computation is exact, they are computationally expensive, which diminishes their usefulness for large-scale models and/or time-critical applications. In this paper, we propose the fast wavefront propagation (FWP) framework for improving the performance of both the MMP and CH algorithms. Unlike the original algorithms that propagate only a single window (a data structure locally encodes geodesic information) at each iteration, our method organizes windows with a bucket data structure so that it can process a large number of windows simultaneously without compromising wavefront quality. Thanks to its macro nature, the FWP method is less sensitive to mesh triangulation than the MMP and CH algorithms. We evaluate our FWP-based MMP and CH algorithms on a wide range of large-scale real-world models. Computational results show that our method can improve the speed by a factor of 3-10.

The skeleton of a 2D shape is an important geometric structure in pattern analysis and computer vision. In this paper we study the skeleton of a 2D shape in a two-manifold M, based on a geodesic metric. We present a formal definition of the skeleton S(\Omega) for a shape V in M and show several properties that make S(\Omega) distinct from its Euclidean counterpart in R^2. We further prove that for a shape sequence {\Omega_i} that converge to a shape V in M, the mapping \Omega\rightarrow S(\Omega_i) is lower semi-continuous. A direct application of this result is that we can use a set P of sample points to approximate the boundary of a 2D shape V in M, and the Voronoi diagram of P inside \Omega\subset M gives a good approximation to the skeleton S(\Omega). Examples of skeleton computation in topography and brain morphometry are illustrated.

The medial axis is an important shape representation that finds a wide range of applications in shape analysis. For large-scale shapes of high resolution, a progressive medial axis representation that starts with the lowest resolution and gradually adds more details is desired. In this paper, we propose a fast and robust geometric algorithm that computes progressive medial axes of a large-scale planar shape. The key ingredient of our method is a novel structural analysis of merging medial axes of two planar shapes along a shared boundary. Our method is robust by separating the analysis of topological structure from numerical computation. Our method is also fast and we show that the time complexity of merging two medial axes is O(n log nv), where n is the number of total boundary generators, nv is strictly smaller than n and behaves as a small constant in all our experiments. Experiments on large-scale polygonal data and comparison with state-of-the-art methods show the efficiency and effectiveness of the proposed method.

Let $K/k$ be a finite Galois extension and $\pi = \fn{Gal}(K/k)$. An algebraic torus $T$ defined over $k$ is called a $\pi$-torus if $T\times_{\fn{Spec}(k)} \fn{Spec}(K)\simeq \bm{G}_{m,K}^n$ for some integer $n$. The set of all algebraic $\pi$-tori defined over $k$ under the stably birational equivalence forms a semigroup, denoted by $T(\pi)$. We will give a complete proof of the following theorem due to Endo and Miyata \cite{EM4}. Theorem. Let $\pi$ be a finite group. Then $T(\pi)\simeq C(\Omega_{\bm{Z}\pi})$ where $\Omega_{\bm{Z}\pi}$ is a maximal $\bm{Z}$-order in $\bm{Q}\pi$ containing $\bm{Z}\pi$ and $C(\Omega_{\bm{Z}\pi})$ is the locally free class group of $\Omega_{\bm{Z}\pi}$, provided that $\pi$ is isomorphic to one of the following four types of groups : $C_n$ ($n$ is any positive integer), $D_m$ ($m$ is any odd integer $\ge 3$), $C_{q^f}\times D_m$ ($m$ is any odd integer $\ge 3$, $q$ is an odd prime number not dividing $m$, $f\ge 1$, and $(\bm{Z}/q^f\bm{Z})^{\times}=\langle \bar{p}\rangle$ for any prime divisor $p$ of $m$), $Q_{4m}$ ($m$ is any odd integer $\ge 3$, $p\equiv 3 \pmod{4}$ for any prime divisor $p$ of $m$).

Morphing is the process of changing a geometric model or an image into another. The process generally involves rigid body motions and non-rigid deformations. It is well known that there exists a unique conformal mapping from a simply connected surface into a unit disk by the Riemann mapping theorem. On the other hand, a 3D surface deformable model can be built via various approaches such as mutual parameterization from direct interpolation or surface matching using landmarks. In this paper, a numerical methods of 3D surface morphing based on deformable model and conformal mapping is demonstrated. We take the advantage of the unique representation of 3D surfaces by the mean curvatures $H$ and the conformal factors $\lambda$ associated with the Riemann mapping and build up the deformation model by consistently registering the landmarks on the conformal parametric domains. As a result, the correspondence of the $(H, \lambda)$ between two surfaces can be defined and a 3D deformation field can be reconstructed. Furthermore, by composition of the M\"obius transformation and the 3D deformation field, a smooth morphing sequence can be generated over a consistent mesh structure via the cubic spline homotopy. Several numerical experiments on the face morphing are presented to demonstrate the robustness of our approach.