Extreme points of Riccati inequalities

Relations between solutions of the algebraic Riccati equation and the associated quadratic matrix inequalities are discussed and explained.     

满足二维空间邻接条件的遗传聚类算法研究

分析了目前满足二维空间邻接条件聚类算法的不足。从聚类概念出发,重新定义了满足二维空间邻接条件聚类的概念。面对满足二维空间邻接条件的聚类问题,定义了邻接矩阵的概念。以邻近距离和邻接矩阵为样本划分依据,以类内平方误差和（WGSS）为聚类目标函数,引入遗传算法,提出满足二维空间邻接条件的遗传聚类算法。通过实例进行了算法测试,并与模糊聚类（FCM）结果进行比较。     

Connectivity in the regular polytope representation

In order to be able to draw inferences about real world phenomena from a representation expressed in a digital computer, it is essential that the representation should have a rigorously correct algebraic structure. It is also desirable that the underlying algebra be familiar, and provide a close modelling of those phenomena. The fundamental problem addressed in this paper is that, since computers do not support real-number arithmetic, the algebraic behaviour of the representation may not be correct, and cannot directly model a mathematical abstraction of space based on real numbers. This paper describes a basis for the robust geometrical construction of spatial objects in computer applications using a complex called the “Regular Polytope”. In contrast to most other spatial data types, this definition supports a rigorous logic within a finite digital arithmetic. The definition of connectivity proves to be non-trivial, and alternatives are investigated. It is shown that these alternatives satisfy the relations of a region connection calculus (RCC) as used for qualitative spatial reasoning, and thus introduce the rigor of that reasoning to geographical information systems. They also form what can reasonably be termed a “Finite Boolean Connection Algebra”. The rigorous and closed nature of the algebra ensures that these primitive functions and predicates can be combined to any desired level of complexity, and thus provide a useful toolkit for data retrieval and analysis. The paper argues for a model with two and three-dimensional objects that have been coded in Java and which implement a full set of topological and connectivity functions which is shown to be complete and rigorous.     

Maximal matching polytope in trees

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.     

Cliques, holes and the vertex coloring polytope

Certain subgraphs of a given graph G restrict the minimum number χ(G) of colors that can be assigned to the vertices of G such that the endpoints of all edges receive distinct colors. Some of such subgraphs are related to the celebrated Strong Perfect Graph Theorem, as it implies that every graph G contains a clique of size χ(G), or an odd hole or an odd anti-hole as an induced subgraph. In this paper, we investigate the impact of induced maximal cliques, odd holes and odd anti-holes on the polytope associated with a new 0-1 integer programming formulation of the graph coloring problem. We show that they induce classes of facet defining inequalities.     

Gradient elements of the knapsack polytope

The knapsack problem is a classical NP-hard problem of special interest in combinatorial mathematics and complexity theory. Particularly interesting are the properties of the knapsack problem domain. In this paper we study the set of gradient elements of the knapsack polytope. They are related with the well-known greedy algorithm for finding approximate solutions to the optimization knapsack problem and constitute an important subset of the extremal elements (vertices) of the knapsack polytope. We obtain a tight bound for the number of distinct gradient elements, which is an exponential function of the problem dimension. We also use the greedy-algorithmic approach and the concept of gradient elements to devise a polynomial algorithm for a large subclass of a linear Diophantine problem which is a variant of the knapsack problem. Some optimization issues related to the problems considered are discussed as well. Received: September 1999 / Accepted: December 2000     

Extreme points of a large 3D point set along multiple directions

In reverse engineering CAD modeling, a facet model is usually constructed from a large point cloud data which are obtained from a surface scanning process. The number of points in the point cloud data may range from hundred thousands to several millions depending on the user-defined precision. As a result, the facet model becomes very ‘large’ in terms of number of facets or vertices. The computational effort required to manipulate such a large set of data becomes enormous. This effort is significant even for some simple operations, e.g. rotating, scaling and translation. In this paper, an algorithm is proposed to determine the extreme points in a large 3D point set along multiple directions. This algorithm uses a cylindrical grid approximation technique to give both approximate solution and exact solution. This algorithm can be used to accelerate the computational process of some geometric problems on a large model, e.g., the minimum bounding box of a facet model [Comput Aid Des 20 (1988) 506; Comput Struct 79I (2001) 1433; Int J Comput Inform Sci 14 (1985) 183] and the ‘fitness’ problem of a model into a bounded volume [Comput Aid Des 20 (1988) 506].     

On fractional faces of the metric polytope

The integrality recognition problem is considered on a sequence M _{n, k} of nested relaxations of a Boolean quadric polytope, including the rooted semimetric M _n and metric M _{n, 3} polytopes. The constraints of the metric polytope cut off all faces of the rooted semimetric polytope that contain only fractional vertices. This makes it possible to solve the integrality recognition problem on M _n in polynomial time. To solve the integrality recognition problem on the metric polytope, we consider the possibility of cutting off all fractional faces of M _{n, 3} by a certain relaxation M _{n, k} . The coordinates of points of the metric polytope are represented in homogeneous form as a three-dimensional block matrix. We show that in studying the question of cutting off the fractional faces of the metric polytope, it is sufficient to consider only constraints in the form of triangle inequalities.     

Estimation of the epipole using optical flow at antipodal points

We present algorithms for estimating the epipole or direction of translation of a moving camera. We use constraints arising from two points that are antipodal on the image sphere in order to decouple rotation from translation. One pair of antipodal points constrains the epipole to lie on a plane, and two such pairs will correspondingly give two planes. The intersection of these two planes is an estimate of the epipole. This means we require image motion measurements at two pairs of antipodal points to obtain an estimate. Two classes of algorithms are possible and we present two simple yet extremely robust algorithms representative of each class. These are shown to have comparable accuracy with the state of the art when tested in simulation under noise and with real image sequences.     

Laplacian versus adjacency matrix in quantum walk search

A quantum particle evolving by Schrödinger’s equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace’s operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.     

Resource placement with multiple adjacency constraints in k-aryn-cubes

The problem of placing resources in a k-ary n-cube (k>2) is considered in this paper. For a given j⩾1, resources are placed such that each nonresource node is adjacent to j resource nodes. We first prove that perfect j-adjacency placements are impossible in k-ary n-cubes if nr-1=2n/j. In each case, we describe an algorithm to obtain perfect j-adjacency placements. We also show that these algorithms can be extended under certain conditions to place j distinct types of resources in a such way that each nonresource node is adjacent to a resource node of each type. For the cases when perfect j-adjacency placements are not possible, we consider approximate j-adjacency placements. We show that the number of copies of resources required in this case either approaches a theoretical lower bound on the number of copies required for any j-adjacency placement or is within a constant factor of the theoretical lower bound for large k     

On the complexity of computing the diameter of a polytope

We show that it isD ^P -hard to determine the combinatorial diameter of a polytope specified by linear inequalities with integer data. Our result partially resolves a long-term open question.     

Force polytope and force ellipsoid for redundant manipulators

Evaluation of force/motion capabilities for a manipulator is useful both in the design phase and in the operational phase. Manipulability ellipsoids and polytopes are well-known tools used to represent these capabilities graphically. This article focuses on the evaluation of force capabilities for redundant manipulators, for which additional constraints must be imposed on the available joint torques to satisfy the static assumption. An algorithm to correctly evaluate the task space force polytope is given and a new definition of the force ellipsoid is proposed. The obtained results can be applied also to nonredundant manipulators in singular configurations. Numerical results are provided in the case of a planar redundant arm. ©1997 John Wiley & Sons, Inc.     

Stochastic models of transport flow interaction at transshipment points

Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 101–112, January–February, 1993.     

On the ordering of optimal hedging points in a class ofmanufacturing flow control models

The optimal flow control policy of a single-product unreliable manufacturing system that must meet a constant demand rate is known to be a threshold type policy: safety production surplus levels called hedging points (thresholds) are associated with each discrete stochastic capacity state of the system and serve to protect the production process from uncertainty in future capacity availability. This correspondence extends and generalizes previous results on the ordering of optimal hedging points. The authors' method is based on examining special properties of the Bellman optimality conditions of the underlying stochastic control problem     

Steganalysis by subtractive pixel adjacency matrix and dimensionality reduction

Subtractive pixel adjacency matrix(SPAM)features,introduced by Pevn′y et al.as a type of Markov chain features,are widely used for blind steganalysis in the spatial domain.In this paper,we present three improvements to SPAM as follows:1)new features based on parallel subtractive pixels are added to the SPAM features,which only refer to collinear subtractive pixels;2)features are extracted not only from the spatial image,but also from its grayscale-inverted image,making the feature matrices symmetrical and reducing their dimensionality by about half;and 3)a new kind of adjacency matrix is used,thereby reducing about 3/4 of the dimensionality of the features.Experimental results show that these methods for dimensionality reduction are very effective and that the proposed features outperform SPAM.     

Summary statistics for measuring the relationship among three types of points in multivariate point patterns

In multivariate spatial point patterns’ statistical analysis, conventional summary statistics can only detect the dependence between two types of points, and cannot be used to detect the dependence among three types of points. New summary statistics are proposed which can be used to detect the influence of the presence the kth type points on the relationship between the ith and the jth type points when the relationship between the ith and the jth type points is positive correlation (or negative correlation, or no spatial interaction), can also be used to infer information about the type of correlation and the range of interaction in multivariate point patterns. In order to reduce the edge-effects the border method to estimate the proposed summary statistics is applied. A simulation and a real example are used to illustrate the proposed methodologies.