Three-dimensional beta shapes

The Voronoi diagram of a point set has been extensively used in various disciplines ever since it was first proposed. Its application realms have been even further extended to estimate the shape of point clouds when Edelsbrunner and Mücke introduced the concept of α-shape based on the Delaunay triangulation of a point set.In this paper, we present the theory of β-shape for a set of three-dimensional spheres as the generalization of the well-known α-shape for a set of points. The proposed β-shape fully accounts for the size differences among spheres and therefore it is more appropriate for the efficient and correct solution for applications in biological systems such as proteins.Once the Voronoi diagram of spheres is given, the corresponding β-shape can be efficiently constructed and various geometric computations on the sphere complex can be efficiently and correctly performed. It turns out that many important problems in biological systems such as proteins can be easily solved via the Voronoi diagram of atoms in proteins and β-shapes transformed from the Voronoi diagram.     

Triangulation of molecular surfaces

Given a molecule, which consists of a set of atoms, a molecular surface is defined for a spherical probe approximating a solvent molecule. Molecular surface is used for both the visualization of the molecule and the computation of various molecular properties such as the area and volume of a protein, which are important for studying problems such as protein docking and folding.In this paper, we present an O(n) time algorithm, in the worst case, for triangulating molecular surface based on the combinatorial information provided by the β-shape of the molecule with n atoms. The proposed algorithm takes advantage of the concise representation of topology among atoms stored in the β-shape.A molecular surface consists of two parts: a blending surface consisting of blending patches and a (solvent) contact surface consisting of (solvent) contact patches. For each blending patch, the algorithm uses compact masks for the construction of a triangular mesh in O(c^′) time in the worst case, where c^′ is the number of point evaluations on the blending patch. For each contact patch, the algorithm uses a template, for each atom type, for the triangulation of the boundary of the atom. Then, the triangular mesh is trimmed off by hyperplanes where each hyperplane corresponds to an arc of the boundary of the contact patch. The triangulation of a contact patch takes O(c^″) time in the worst case, where c^″ is the number of point evaluations on the boundary of an atom. Since there are at most O(n) patches, the worst case time complexity is O(n).The proposed algorithm also handles internal voids and guarantees the watertightness of the produced triangular mesh of a molecular surface. In addition, the level-of-detail is easily achieved as a by-product of the proposed scheme. The proposed algorithm is fully implemented and statistics from experiments are also collected.     

Loop subdivision surfaces interpolating -spline curves

This paper presents a novel method for defining a Loop subdivision surface interpolating a set of popularly-used cubic B-spline curves. Although any curve on a Loop surface corresponding to a regular edge path is usually a piecewise quartic polynomial curve, it is found that the curve can be reduced to a single cubic B-spline curve under certain constraints of the local control vertices. Given a set of cubic B-spline curves, it is therefore possible to define a Loop surface interpolating the input curves by enforcing the interpolation constraints. In order to produce a surface of local or global fair effect, an energy-based optimization scheme is used to update the control vertices of the Loop surface subjecting to curve interpolation constraints, and the resulting surface will exactly interpolate the given curves. In addition to curve interpolation, other linear constraints can also be conveniently incorporated. Because both Loop subdivision surfaces and cubic B-spline curves are popularly used in engineering applications, the curve interpolation method proposed in this paper offers an attractive and essential modeling tool for computer-aided design.     

Kernel modeling for molecular surfaces using a uniform solution

In this paper, a rational Bézier surface is proposed as a uniform approach to modeling all three types of molecular surfaces (MS): the van der Waals surface (vdWS), solvent accessible surface (SAS) and solvent excluded surface (SES). Each molecular surface can be divided into molecular patches, which can be defined by their boundary arcs. The solution consists of three steps: topology modeling, boundary modeling and surface modeling. Firstly, using a weighted α-shape, topology modeling creates two networks to describe the neighboring relationship of the molecular atoms. Secondly, boundary modeling derives all boundary arcs from the networks. Thirdly, surface modeling constructs all three types of molecular surfaces patch-by-patch, based on the networks and the boundary arcs. For an SES, the singularity is specially treated to avoid self-intersections. Instead of approximation, this proposed solution can produce precise shapes of molecular surfaces. Since rational Bézier representation is much simpler than a trimmed non-uniform rational B-spline surface (NURBS), computational load can be significantly saved when dealing with molecular surfaces. It is also possible to utilize the hardware acceleration for tessellation and rendering of a rational Bézier surface. CAGD kernel modelers typically use NURBSs as a uniform representation to handle different types of free-form surface. This research indicates that rational Bézier representation, more specifically, a bi-cubic or 2×4 rational Bézier surface, is sufficient for kernel modeling of molecular surfaces and related applications.     

Recognition of docking sites on a protein using β-shape based on Voronoi diagram of atoms

A protein consists of atoms. Given a protein, the automatic recognition of depressed regions on the surface of the protein, often called docking sites or pockets, is important for the analysis of interaction between a protein and a ligand and facilitates fast development of new drugs.Presented in this paper is a geometric approach for the detection of docking sites using β-shape which is based on the Voronoi diagram for atoms in Euclidean distance metric. We first propose a geometric construct called a β-shape which represents the proximity among atoms on the surface of a protein. Then, using the β-shape, which takes the size differences among different atoms into account, we present an algorithm to extract the pockets for the possible docking site on the surface of a protein.     

The -basis and implicitization of a rational parametric surface

The concept of a μ-basis was introduced in the case of parametrized curves in 1998 and generalized to the case of rational ruled surfaces in 2001. The μ-basis can be used to recover the parametric equation as well as to derive the implicit equation of a rational curve or surface. Furthermore, it can be used for surface reparametrization and computation of singular points. In this paper, we generalize the notion of a μ-basis to an arbitrary rational parametric surface. We show that: (1) the μ-basis of a rational surface always exists, the geometric significance of which is that any rational surface can be expressed as the intersection of three moving planes without extraneous factors; (2) the μ-basis is in fact a basis of the moving plane module of the rational surface; and (3) the μ-basis is a basis of the corresponding moving surface ideal of the rational surface when the base points are local complete intersections. As a by-product, a new algorithm is presented for computing the implicit equation of a rational surface from the μ-basis. Examples provide evidence that the new algorithm is superior than the traditional algorithm based on direct computation of a Gröbner basis. Problems for further research are also discussed.     

Connolly Surface on an Atomic Structure via Voronoi Diagram of Atoms

One of the most important geometric structures of a protein is the Connolly surface of protein since a Connolly surface plays an important role in protein folding, docking, interactions between proteins, amongst other things. This paper presents an algorithm for precisely and efficiently computing the Connolly surface of a protein using a proposed geometric construct called β-shape based on the Voronoi diagram of atoms in the protein. Given the Voronoi diagram of atoms based on the Euclidean distance from the atom surfaces, the proposed algorithm first computes a β-shape with an appropriate probe. Then, the Connolly surface is computed by employing the blending operation on the atomic complex of the protein by the given probe.     

Finding an Euclidean anti--centrum location of a set of points

An obnoxious facility is to be located inside a polygonal region of the plane, maximizing the sum of the k smallest weighted Euclidean distances to n given points, each protected by some polygonal forbidden region. For the unweighted case and k fixed an O(n²logn) time algorithm is presented. For the weighted case a thorough study of the relevant structure of the multiplicatively weighted order-k-Voronoi diagram leads to the design of an O(kn³+n³logn) time algorithm for finding an optimal solution to the anti-t-centrum problem for every t=1,…,k, simultaneously.     

A vertex-first parametric algorithm for polyhedron blending

This paper enhances the conventional parametric algorithms for polyhedron blending, by strategically inverting the edges-first approach to vertex-first, so that matching the vertex blending surface (using a triangular or tensor product Bézier surface, or an S-patch) with the edge blending surfaces (generated by Hartmann method) becomes essentially easier. Based on a study of cross boundary derivatives (those of S-patches are deduced herein), G^g-continuity between all the above surfaces and the primary planar faces is achieved by a novel trick as a first step: assigning the vertex, some edge points and some face points to be the proper control points. This still leaves enough free parameters usable for changing the blending configuration. The new algorithm is illustrated with two practical examples involving miscellaneous vertices up to 6-edge convex–concave.     

Assembling curvature continuous surfaces from triangular patches

We assemble triangular patches of total degree at most eight to form a curvature continuous surface. The construction illustrates how separation of local shape from representation and formal continuity yields an effective construction paradigm in partly underconstrained scenarios. The approach localizes the technical challenges and applies the spline approach, i.e. keeping the degree fixed but increasing the number of pieces, to deal with increased complexity when many patches join at a central point.     

New applications of clique separator decomposition for the Maximum Weight Stable Set problem

Graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tarjan as a divide-and-conquer approach for solving various problems such as the Maximum Weight Stable Set (MWS) problem, Colouring and Minimum Fill-in. The basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. We give new examples where the clique separator decomposition works well for the MWS problem; our results improve and extend various recently published results. In particular, we describe the atom structure for some new classes of graphs whose atoms are P₅-free (the P₅ is the induced path with five vertices) and obtain new polynomial time results for the MWS problem. The complexity of this problem on the class of P₅-free graphs is still unknown.     

Existence of positive solutions for th-order singular superlinear boundary value problems

This paper investigates the existence of positive solutions for 2nth-order (n>1) singular superlinear boundary value problems. A necessary and sufficient condition for the existence of C²ⁿ⁻²[0,1] as well as C²ⁿ⁻¹[0,1] positive solutions is given by constructing a special cone and with the e-Norm.     

Dual periodicity in -norm minimisation problems

The topic of this paper is the discrete-time l₁-norm minimisation problem with convolution constraints. We find primal initial conditions for which the dual optimal solution is periodic. Periodicity of the dual optimal solution implies satisfaction of a simple linear recurrence relation by the primal optimal solution.     

An involute spiral that matches Hermite data in the plane

A construction is given for a planar rational Pythagorean hodograph spiral, which interpolates any two-point G² Hermite data that a spiral can match. When the curvature at one of the points is zero, the construction gives the unique interpolant that is an involute of a rational Pythagorean hodograph curve of the form cubic over linear. Otherwise, the spiral comprises an involute of a Tschirnhausen cubic together with at most two circular arcs. The construction is by explicit formulas in the first case, and requires the solution of a quadratic equation in the second case.     

On the surface area of the -star graph

We present an explicit formula for the surface area of the (n,k)-star graph, i.e., the number of nodes at a certain distance from the identity node in the graph, by identifying the unique cycle structures associated with the nodes in the graph, deriving a distance expression in terms of such structures between the identity node of the graph and any other node, and enumerating those cycle structures satisfying the distance restriction.The above surface area derivation process can also be applied to some of the other node symmetric interconnection structures defined on the symmetric group, when the aforementioned distance expression is available.     

On standard control problems for systems with infinitely many unstable poles

In this paper, H^∞ control for a class of linear time invariant systems with infinitely many unstable poles is studied. An example of such a plant is a high gain system with delayed feedback. We formulate the problem via a generalized plant which consists of a rational transfer matrix and the inverse of a scalar (possibly irrational) inner function. It is shown that the problem can be decomposed into a finite-dimensional H^∞ control problem and an additional rank condition.     

Shape-preserving interpolation of irregular data by bivariate curvature-based cubic splines in spherical coordinates

We investigate C¹-smooth bivariate curvature-based cubic L₁ interpolating splines in spherical coordinates. The coefficients of these splines are calculated by minimizing an integral involving the L₁ norm of univariate curvature in four directions at each point on the unit sphere. We compare these curvature-based cubic L₁ splines with analogous cubic L₂ interpolating splines calculated by minimizing an integral involving the square of the L₂ norm of univariate curvature in the same four directions at each point. For two sets of irregular data on an equilateral tetrahedron with protuberances on the faces, we compare these two types of curvature-based splines with each other and with cubic L₁ and L₂ splines calculated by minimizing the L₁ norm and the square of the L₂ norm, respectively, of second derivatives. Curvature-based cubic L₁ splines preserve the shape of irregular data well, better than curvature-based cubic L₂ splines and than second-derivative-based cubic L₁ and L₂ splines. Second-derivative-based cubic L₂ splines preserve shape poorly. Variants of curvature-based L₁ and L₂ splines in spherical and general curvilinear coordinate systems are outlined.     

Powers in a class of -strict standard episturmian words

This paper concerns a specific class of strict standard episturmian words whose directive words resemble those of characteristic Sturmian words. In particular, we explicitly determine all integer powers occurring in such infinite words, extending recent results of Damanik and Lenz [D. Damanik, D. Lenz, Powers in Sturmian sequences, European J. Combin. 24 (2003) 377–390, doi:10.1016/S0195-6698(03)00026-X], who studied powers in Sturmian words. The key tools in our analysis are canonical decompositions and a generalization of singular words, which were originally defined for the ubiquitous Fibonacci word. Our main results are demonstrated via some examples, including the k-bonacci word, a generalization of the Fibonacci word to a k-letter alphabet (k≥2).     

Suboptimal robust synthesis for MIMO plant under coprime factor perturbations

Suboptimal robust synthesis for MIMO nominal system under coprime factor perturbations is considered in classical and non-classical statements. In the classical statement, weights of perturbations and upper bound on magnitude bounded exogenous disturbance are assumed to be known to controller designer. Suboptimal synthesis within ε tolerance is reduced to the solution of log₂(1/ε) standard mixed sensitivity problems of ℓ₁ optimization. In the non-classical statement, the upper bounds on perturbations and exogenous disturbance are to be estimated from measurement data and suboptimal synthesis is reduced to the solution of 1/ε mixed sensitivity problems.     

Isolation concepts for efficiently enumerating dense subgraphs

In an undirected graph G=(V,E), a set of k vertices is called c-isolated if it has less than ck outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all c-isolated maximal cliques in O(4^cc⁴|E|) time. We extend this to enumerating all maximal c-isolated cliques (which are a superset) and improve the running time bound to O(2.89^cc²|E|), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s-plex is the parameter and a fixed-parameter algorithm for enumerating isolated s-plexes when the parameter describes the degree of isolation.