Regular algebraic curve segments (III) - applications in interactive design and data fitting
In this paper (part three of the trilogy) we use low degree G 1 and G 2 continuous regular algebraic spline curves defined within parallelograms, to interpolate an ordered set of data points in the plane. We explicitly characterize curve families whose members have the required interpolating properties and possess a minimal number of inflection points. The regular algebraic spline curves considered here have many attractive features: They are easy to construct. There exist convenient geometric control handles to locally modify the shape of the curve. The error of the approximation is controllable. Since the spline curve is always inside the parallelogram, the error of the fit is bounded by the size of the parallelogram. The spline curve can be rapidly displayed, even though the algebraic curve segments are implicitly defined.

title: Automatic reconstruction of surfaces and scalar fields from 3D scans
abstract: We present an efficient and uniform approach for the automatic reconstruction of surfaces of CAD (computer aided design) models and scalar fields defined on them, from an unorganized collection of scanned point data. A possible application is the rapid computer model reconstruction of an existing part or prototype from a three dimensional (3D) points scan of its surface. Color, texture or some scalar material property of the physical part, define natural scalar fields over the surface of the CAD model. Our reconstruction algorithm does not impose any convexity or differentiability restrictions on the surface of the original physical part or the scalar field function, except that it assumes that there is a sufficient sampling of the input point data to unambiguously reconstruct the CAD model. Compared to earlier methods our algorithm has the advantages of simplicity, efficiency and uniformity (both CAD model and scalar field reconstruction). The simplicity and efficiency of our approach is based on several novel uses of appropriate sub-structures (alpha shapes) of a three-dimensional Delaunay Triangulation, its dual the three-dimensional Voronoi diagram, and dual uses of trivariate Bernstein-Bezier forms. The boundary of the CAD model is modeled using implicit cubic Bernstein-Bezier patches, while the scalar field is reconstructed with functional cubic Bernstein-Bezier patches.

title: Spline Approximations of Real Algebraic Surfaces
abstract: We use a combination of both symbolic and numerical techniques to construct several degree boundedG0andG1continuous, piecewise spline approximations of real implicit algebraic surfaces for both computer graphics and geometric modeling. These approximations are based upon an adaptive triangulation (aG0planar approximation) of the real components of the algebraic surface, and include both singular points and singular curves on the surface. A curvilinear wireframe is also constructed using minimum bending energy, parametric curves with additionally normals varying along them. The spline approximations over the triangulation or curvilinear wireframe could be one of several forms: either low degree, implicit algebraic splines (triangular A-patches) or multivariate functional B-splines (B-patches) or standardized rational Bernstein?Bezier patches (RBB), or triangular rational B-Splines. The adaptive triangulation is additionally useful for a rapid display and animation of the implicit surface.

title: Fast evaluation of the improved Loop's subdivision surfaces
abstract: For obtaining better curvature distributions of subdivision surfaces, various improvements for Loop's subdivision scheme (C. Loop, 1987) on triangular surface meshes have been made. A careful analysis shows that the fast evaluation technique of the subdivision surface proposed by Stam is no longer usable to these improved schemes. This paper describes a fast evaluating algorithm for improved Loop's subdivision surfaces. The algorithm is applicable to a vast class of subdivision schemes for triangular surface meshes. Using the proposed algorithm, one can evaluate the subdivision surface at any domain point for any set of input subdivision masks and a control mesh.

title: Directional smoothing of triangular meshes
abstract: In this paper, we propose a so-called directional smoothing method based mean curvature flow. The selection of the diffusion direction is based on the descent of some energy functional. We show that the directional diffusion flow is volume-preserving. Based on the local directional diffusion flow, we present a feature-preserving smoothing method. Finally, we provide a series of examples to graphically demonstrate the quality of our results.

title: Smooth Shell Construction with Mixed Prism Fat Surfaces
abstract: Several naturally occurring as well as manufactured objects have shell like structures, that is their boundaries consist of surfaces with thickness. In an earlier paper, we have provided a reconstruction algorithm for such shell structures using smooth fat surfaces within three-sided prisms. In this paper, we extend the approach to a scaffolding consisting of three and four-sided prisms. Within each prism the constructed function is converted to a spline representation. In addition to the adaptive feature of our earlier scheme, the new scheme has the following extensions: (a) four sided fat patches are employed; (b) the size of individual fat patches are bigger; (c) fairing techniques are combined to obtain nicely shaped fat surfaces.

title: Human action recognition with primitive-based coupled-HMM
abstract: This paper presents a new approach named primitive-based coupled-HMM for human natural complex action recognition. First, the system proposes a hybrid human model and employs 2-order B-spline function to detect the two shoulder joints in the silhouette image to obtain the basic motion features including the elbow angles, motion parameters of the face and two hands. Then, primitive-based coupled hidden Markov model (PCHMM) is presented for natural context-dependent action recognition. Lastly, comparison experiments show that PCHMM is better than the conventional HMM and coupled HMM.

title: Power domination in block graphs
abstract: The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 2002, Haynes et al. considered the graph theoretical representation of this problem as a variation of the domination problem. They defined a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number γp(G) of a graph G is the minimum cardinality of a power dominating set of G. This problem was proved NP-complete even when restricted to bipartite graphs and chordal graphs. In this paper, we present a linear time algorithm for solving the power domination problem in block graphs. As an application of the algorithm, we establish a sharp upper bound for power domination number in block graphs and characterize the extremal graphs.

title: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
abstract: In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying a penalty. Existing approaches [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers,  2001, p. 642] and [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP,  (2003) 795] for this variant of facility location problem are all based on primal-dual method. In this paper, we present an efficient linear programming (LP) rounding based approach to show that LP rounding techniques are equally capable of solving this variant of facility location problem. Our algorithm uses a two-phase filtering technique (generalized from Lin and Vitter's [@?-approximation with minimum packing constraint violation, ) to identify those to-be-rejected clients and open facilities for the remaining ones. Our approach achieves an approximation ratio of 2+2/e (~2.736) which is worse than the best approximation ratio of 2 achieved by the much more sophisticated dual fitting technique [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP,  (2003) 795], but better than the approximation ratio of 3 achieved by the primal-dual method [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers,  2001, p. 642]. Our algorithm is simple, natural, and can be easily integrated into existing LP rounding based algorithms for facility location problem to deal with outliers. problem to deal with outliers.

title: A probabilistic dynamic contour model for accurate and robust lip tracking
abstract: In this paper a new condensation style contour tracking method called probabilistic dynamic contour (PDC) is proposed for lip tracking: a novel mixture dynamic model is designed to represent shape more compactly and to tolerate larger motions between frames, a measurement model is designed to include multiple visual cues. The proposed PDC tracker has the advantage that it is conceptually general but effectively suitable for lip tracking with the designed dynamic and measurement model. The new tracker improves the traditional condensation style tracker in three aspects: Firstly, the dynamic model is partially derived from the image sequence, so the tracker does not need to learn the dynamics in advance. Secondly, the measurement model is easy to be updated during tracking, which avoids modeling the foreground object in prior. Thirdly, to improve the tracker's speed, a compact representation of shape and a noise model are proposed to reduce the samples required to represent the posterior distribution. An experiment on lip contour tracking shows that the proposed method tracks contours robustly as well as accurately compared to the existing tracking method.

title: Acyclic domination on bipartite permutation graphs
abstract: For a graph G = (V, E), a subset S ⊆ V is called an acyclic dominating set of G if every vertex in V - S is adjacent to at least one vertex in S and the subgraph induced by S contains no cycles. In this paper, we present a linear time algorithm for transforming a minimum dominating set in a bipartite permutation graph into a minimum acyclic dominating set. Chao et al. gave a linear time algorithm to find a minimum dominating set of a permutation graph. Thus, we show that the acyclic domination problem is linear time solvable for bipartite permutation graphs.