We present an efficient algorithm for finding the shortest path joining two points in a sequence of triangles in three-dimensional space using the concept of funnels associated with common edges along the sequence of triangles and the planar unfolding for each funnel. We show that the unfolded image of a funnel is a simple polygon, it thus is non-overlapping. Therefore, such funnels are determined iteratively to their associated common edges by the planar unfolding and the shortest path joining two points is determined by cusps of these funnels. 相似文献
Any optimization problem in a finite structure can be represented as an integer or mixed-integer program in integral quantities.We show that, when an optimization problem on an unbounded structure has such a representation, it is very close to a linear programming problem, in the specific sense described in the following results. We also show that, if an optimization problem has such a representation, no more thann+2 equality constraints need be used, wheren is the number of variables of the problem.We obtain a necessary and sufficient condition for a functionf:SZ, withSZn, to have a rational model in Meyer's sense, and show that Ibaraki models are a proper subset of Meyer models.This research was supported by NSF Grant No. GP-37510X1 and ONR Contract No. N00014-75-C0621, NR047-048. 相似文献
In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers
to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge
bounds equal one, stable multi-sets are equivalent to stable sets.
For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient
conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the
stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable
multi-sets and conditions for them to be facet defining are determined.
The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets
emerge as an important substructure in the design of optical networks.
Received: February 14, 2001/Revised version: September 7, 2001 相似文献
For an nonnegative matrix , an isomorphism is obtained between the lattice of initial subsets (of ) for and the lattice of -invariant faces of the nonnegative orthant . Motivated by this isomorphism, we generalize some of the known combinatorial spectral results on a nonnegative matrix that are given in terms of its classes to results for a cone-preserving map on a polyhedral cone, formulated in terms of its invariant faces. In particular, we obtain the following extension of the famous Rothblum index theorem for a nonnegative matrix: If leaves invariant a polyhedral cone , then for each distinguished eigenvalue of for , there is a chain of distinct -invariant join-irreducible faces of , each containing in its relative interior a generalized eigenvector of corresponding to (referred to as semi-distinguished -invariant faces associated with ), where is the maximal order of distinguished generalized eigenvectors of corresponding to , but there is no such chain with more than members. We introduce the important new concepts of semi-distinguished -invariant faces, and of spectral pairs of faces associated with a cone-preserving map, and obtain several properties of a cone-preserving map that mostly involve these two concepts, when the underlying cone is polyhedral, perfect, or strictly convex and/or smooth, or is the cone of all real polynomials of degree not exceeding that are nonnegative on a closed interval. Plentiful illustrative examples are provided. Some open problems are posed at the end.
We investigate slicings of combinatorial manifolds as properly embedded co-dimension 1 submanifolds. Focus is given to the case of dimension 3, where slicings are (discrete) normal surfaces. For the cases of 2-neighborly 3-manifolds as well as quadrangulated slicings, lower bounds on the number of quadrilaterals of slicings depending on its genus g are presented. These are shown to be sharp for infinitely many values of g. Furthermore, we classify slicings of combinatorial 3-manifolds which are weakly neighborly polyhedral maps. 相似文献
In a general measure-theoretic context, it is proved that the action of a stochastic map on a pair of probability distributions can be characterized by the criterion of decreasing mixing distance. 相似文献
We present anO(p · n) algorithm for the problem of finding disjoint simple paths of minimum total length betweenp given pairs of terminals on oriented partial 2-trees withn nodes and positive or negative arc lengths. The algorithm is inO(n) if all terminals are distinct nodes. We characterize the convex hull of the feasible solution set for the casep=2.We gratefully acknowledge the referee's many helpful suggestions to improve the presentation of this paper. 相似文献