10302711
Fast evaluation of the improved Loop's subdivision surfaces
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.
12007064
Quality meshing of implicit solvation models of biomolecular structures
This paper describes a comprehensive approach to construct quality meshes for implicit solvation models of biomolecular structures starting from atomic resolution data in the Protein Data Bank (PDB). First, a smooth volumetric electron density map is constructed from atomic data using weighted Gaussian isotropic kernel functions and a two-level clustering technique. This enables the selection of a smooth implicit solvation surface approximation to the Lee-Richards molecular surface. Next, a modified dual contouring method is used to extract triangular meshes for the surface, and tetrahedral meshes for the volume inside or outside the molecule within a bounding sphere/box of influence. Finally, geometric flow techniques are used to improve the surface and volume mesh quality. Several examples are presented, including generated meshes for biomolecules that have been successfully used in finite element simulations involving solvation energetics and binding rate constants.
15712433
Convergence analysis of a discretization scheme for Gaussian curvature over triangular surfaces
In this paper, we study the convergence property of a well known discretized scheme for approximating Gaussian curvature, derived from Gauss-Bonnet theorem, over triangulated surface. Suppose the triangulation is obtained from a sampling of a smooth parametric surface, we show theoretically that the approximation has quadratic convergence rate if the surface sampling satisfies the so-called parallelogram criterion. Numerical results which justify the theoretical analysis are also presented.
718597
Error bounded regular algebraic spline curves
i=0 Pn n=0 bijB m i (u)B n j (v) of bi-degree (m;n) has total degree m + n, however, the class of Gmn(u; v) is a subset of polynomials of total degree m + n. G (resp G) continuity implies curve segments share the same tangent(curvature) at join points(knots). In each of the G and G constructions, we develop a spline curve family whose member satis es given interpolation conditions. Each family depends on one free parameter that is related linearly to coe cients of Gmn(u; v). Compared with A-spline segments de ned in triangular (barycentric) BB-form [2], these algebraic curve segments in tensor product form have the following distinct features: (a) They are easy to construct. The coe cients of the bivariate polynomial that de ne the curve are explicitly given. (b) There exist convenient geometric control handles to locally modify the shape of the curve, essential for interactive curve design. (c) The spline curves, for the rectangle scheme, are -error controllable where is the prespeci ed width of the rectangle. This feature is especially important for tting to \noisy" data with uncertainty. (d) These splines curves have a minimal number of in ection points. Each curve segment of the spline curve has either no in ection points if the corresponding edge is convex, or one in ection point otherwise, and the join points of the curve segments are not in ection points. (e). Since the required bi-degree (m;n) for G and G is low(in this paper, minfm;ng 2), the curve can be evaluated and displayed extremely fast. We explore both display via parameterization as well as recursive subdivision techniques(see [11]). (f) In the six spline families we discuss in sections 2 and 3, there are four cases with minfm;ng = 1. In these cases, rational parametric expressions are easily derived. Hence, for
14215306
Hidden Markov Model Based Events Detection in Soccer Video
This paper presents an algorithm developed based on hidden Markov model for cues fusion and event inference in soccer video. Four events, shoot, foul, offside and normal playing, are defined to be detected. The states of the events are employed to model the observations of the five cues, which are extracted from the shot sequences directly. The experimental results show the algorithm is effective and robust in inferring events from roughly extracted cues.
205481438
Acyclic domination on bipartite permutation graphs
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.
2490006
An LP rounding algorithm for approximating uncapacitated facility location problem with penalties
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, in: Proc. Symposium on Discrete Algorithms, 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, J. ACM 50 (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, in: Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, p. 771]) 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, J. ACM 50 (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, in: Proc. Symposium on Discrete Algorithms, 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.
11706299
An Efficient Algorithm for Determining 3-D Bi-plane Imaging Geometry
Biplane projection imaging is one of the primary methods for imaging and visualizing the cardiovascular systems in medicine. A key problem in such a technique is to determine the imaging geometry (i.e., the rotation and translation) of two projections so that the 3-D structure can be accurately reconstructed. Based on interesting observations and efficient geometric techniques, we present in this paper a new algorithmic solution for this problem. Comparing with existing optimization-based approaches, our technique yields better accuracy, has bounded execution time, and thus is more suitable for on-line applications. Our technique can easily deal with outliers for further improving the accuracy.
22160794
Output hazard-free transition tests for silicon calibrated scan based delay testing
Architectural restrictions of scan greatly limit the effectiveness of traditional scan based delay tests. It has been recently shown that additional testing for delays on short paths using fast clocks can significantly lower DPM. However, accurately obtaining the needed timing information for such tests from simulation is extremely difficult. The simulations must not only accurately account for the effects of process parameter variations, but also power supply noise and crosstalk from the excessive switching activity of scan tests. We suggest that learning signal timing information on silicon to "calibrate" such tests can be much more accurate and cost effective. However, such an approach requires that the outputs of the applied tests be hazard free to avoid learning incorrect timing due to a glitch at the output. Simulation results presented here indicate that such output hazard free test can be obtained with an average coverage only about 10% below the transition delay fault coverage for both launch-on-shift (LOS) and launch-on-capture (LOG) modes