A (k, K) circuit is one which can be decomposed into nonintersecting blocks of gates where each block has no more than K external inputs, such that the graph formed by letting each block be a node and inserting edges between blocks if they share a signal line, is a partial k-tree. (k, K) circuits are special in that they have been shown to be testable in time polynomial in the number of gates in the circuit, and are useful if the constants k and K are small. We demonstrate a procedure to synthesise (k, K) circuits from a special class of Boolean expressions.

In traditional animation, keyframes are modeled and standard graphics pipeline is used to animate the scene. In this paper we consider volume animation where the 3D world and its components are represented as a voxel model. The voxel model is annotated with hierarchical feature information and thus facilitates easy volume editing. These annotations are based on regularised Minkowski operators used in constructing/sculpting the model. The Selective editing of volume models also becomes possible with these annotations. The pure voxel or volumetric approach used from start to finish has the advantage that extremely simple data structures and algorithms enable us to generate complex volume animations.

A new Extensible Markup Language (XML) application, Molecular Dynamics Language (MoDL) has been developed. MoDL provides a simple, but powerful tool for molecular dynamics visualization and has been developed by combining, for the first time, the strengths of XML and the Virtual Reality Modeling Language. The details of MoDL, its implementation and examples of its use are presented in this paper.

Given a set of points on the plane, we study the structure of their rectilinear hull. We also consider the multiple objective decision of identifying a facility location that minimizes the rectilinear distance to each of these points. We show specific correspondences between the efficient (non-dominated) solutions to the location problem and the rectilinear hulls of point sets in the plane. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Gauss and Fourier have together provided us with the essential techniques for symbolic computation with linear arithmetic constraints over the reals and the rationals. These variable elimination techniques for linear constraints have particular significance in the context of constraint logic programming languages that have been developed in recent years. Variable elimination in linear equations (Guassian Elimination) is a fundamental technique in computational linear algebra and is therefore quite familiar to most of us. Elimination in linear inequalities (Fourier Elimination), on the other hand, is intimately related to polyhedral theory and aspects of linear programming that are not quite as familiar. In addition, the high complexity of elimination in inequalities has forces the consideration of intricate specializations of Fourier's original method. The intent of this survey article is to acquaint the reader with these connections and developments. The latter part of the article dwells on the thesis that variable elimination in linear constraints over the reals extends quite naturally to constraints in certain discrete domains.

The class of Horn clause sets in propositional logic is extended to a larger class for which the satisfiability problem can still be solved by unit resolution in linear time. It is shown that to every arborescence there corresponds a family of extended Horn sets, where ordinary Horn sets correspond to stars with a root at the center. These results derive from a theorem of Chandresekaran that characterizes when an integer solution of a system of inequalities can be found by rounding a real solution in a certain way. A linear-time procedure is provided for identifying “hidden” extended Horn sets (extended Horn but for complementation of variables) that correspond to a specified arborescence. Finally, a way to interpret extended Horn sets in applications is suggested.

Bezout's theorem gives an upper bound on the degree of the intersection of properly intersecting algebraic varieties. In spaces of dimension higher than two, however, intersections between many algebraic varieties such as curves are improper. Bezout's theorem cannot be directly used to bound the number of points at which these curves intersect. In this paper an algebrogeometric technique is developed for obtaining an upper bound on the number of intersection points of two irreducible algebraic curves in k -dimensional space. The theorems obtained are applied to the specific case of intersecting algebraic space curves in three-dimensional space, and a number of examples are analyzed in this regard. The implications of the derived results for computer-aided geometric design are discussed.

The intersection of algebraic curves in three and higher dimensional spaces is considered. An algebrogeometric technique is developed for obtaining an upper bound on the number of intersection points of two irreducible algebraic curves. The asymptotic bounds are shown to be a function of only the degrees of the two intersecting curves. Some specific examples involving curves in 3-space are analyzed.

The authors describe a procedure for the automatic design of a preform based on circumscription algorithms. The procedure is defined in general terms and applied to preforms realized by axisymmetric deep-drawing processes. The automatic design procedure is supervised by a 'generate, test, and rectify' tactic. The 'generate' stage hypothesizes a deep-drawn preform that either contains the finished workpiece or is 'close' to doing so. If the workpiece is not fully contained by the initial preform, the latter is 'rectified'. Rectification applies small changes to the radii of bending and to the wall thickness of the hypothesized preform cup. Either rectification continues recursively or a new hypothesis is generate. The cup is defined by its medial and a nominal uniform wall thickness. The design is accepted when a circumscribing cup is produced. The supervisory search mechanism is a combination of A*, hill-climbing, and depth-first.>