A polynomial algorithm for one problem of guillotine cutting

We consider the problem of guillotine cutting a rectangular sheet into two rectangular pieces without rotations. The question is whether there exists a cutting pattern with given numbers of occurrences of both rectangular pieces. A polynomial time algorithm is described to construct the convex hull of solutions to this problem.     

An introduction to preconvexity spaces

Axioms are given for a preconvexity space and certain consequences obtained. In particular, it is shown that in a very natural way, a preconvexity on a space yields an abstract convexity space in much the same manner as a proximity yields a topological space. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the performance of peeling algorithms

The peeling of a d-dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst-case convex hull algorithm, known to have an O(n^˙ Log (n)) execution time, may give an O(n^˙n^˙ Log (n)) to peel all the set; an O(n^˙n) convex hull algorithm, m being the number of extremal points, is shown to peel every set with an O(n-n) time, and proved to be optimal; an implementation of this algorithm is given for planar sets and spatial sets, but the latter give only an approximate O(n^˙n) performance.     

Injective hulls are not natural

In a category with injective hulls and a cogenerator, the embeddings into injective hulls can never form a natural transformation, unless all objects are injective. In particular, assigning to a field its algebraic closure, to a poset or Boolean algebra its Mac-Neille completion, and to an R-module its injective envelope is not functorial, if one wants the respective embeddings to form a natural transformation. Received January 21, 2000; accepted in final form August 10, 2001. RID="h1" RID="h2" RID="h3" ID="h1"The hospitality of York University is gratefully acknowledged by the first author. ID="h2"Third author partially supported by the Grant Agency of the Czech Republic under Grant no. 201/99/0310, and the hospitality of York University is also acknowledged. ID="h3"Partial financial assistance by the Natural Sciences and Engineering Councel of Canada is acknowledged by the fourth author.     

Graphs that are not complete pluripolar

Let be domains in . Under very mild conditions on we show that there exist holomorphic functions , defined on with the property that is nowhere extendible across , while the graph of over is not complete pluripolar in . This refutes a conjecture of Levenberg, Martin and Poletsky (1992).

     

Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets

In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time.     

An interdependency index for the outputs of uncertain systems

The study of mechanical systems with uncertain parameters is gaining increasing interest in the field of system analysis to provide an expedient model for the prediction of the system behavior. Making use of the Transformation Method, the uncertain parameters of the system are modeled by fuzzy numbers in contrast to random numbers used in stochastic approaches. As a result of this analysis, a quantification of the overall uncertainty of the system outputs, including a worst-case scenario, is obtained. The inputs of the resulting fuzzy-valued model are a priori uncorrelated but after the uncertainties are propagated through the model, interdependency (or interaction) between the outputs may arise. If such interdependency is neglected, a misinterpretation of the results may occur. For example, in the case of applying uncertainty analysis in the early design phase of a product to determine the relevant design-parameter space, the interdependency between the design variables may reduce significantly the available part of the design space. This paper proposes a measure of interdependency between the uncertain system outputs. The interdependency index can be derived by a postprocessing of the data gained by the analysis with the Transformation Method. Such information can be obtained by a negligible amount of extra computation time.     

Another complete invariant for Steiner triple systems of order 15

In this note, the 80 non‐isomorphic triple systems on 15 points are revisited from the viewpoint of the convex hull of the characteristic vectors of their blocks. The main observation is that the numbers, of facets of these 80 polyhedra are all different, thus producing a new proof of the non‐isomorphism of these triple systems. The space dimension of these polyhedra is also discussed. Finally, we observe the large number of facets of some of these polyhedra with few vertices, in relation with the upper bound problem for combinatorial polyhedra. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

The rate of convergence for the cyclic projections algorithm III: Regularity of convex sets

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets.In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.