Circular Separability of Polygons

Two planar sets are circularly separable if there exists a circle enclosing one of the sets and whose open interior disk does not intersect the other set. This paper studies two problems related to circular separability. A linear-time algorithm is proposed to decide if two polygons are circularly separable. The algorithm outputs the smallest separating circle. The second problem asks for the largest circle included in a preprocessed, convex polygon, under some point and/ or line constraints. The resulting circle must contain the query points and it must lie in the halfplanes delimited by the query lines. Received October 25, 1998; revised April 21, 1999.     

Monotonicity of linear separability under translation

A set of n pattern vectors are given in d-space and classified arbitrarily into two sets. The sets of patterns are said to be linearly separable if there exists a hyperplane that separates them. We ask whether translation of one of these sets in an arbitrary direction helps separability. Sometimes yes and sometimes no, but yes on the average. The average is taken over all classifications of the patterns into two sets. In fact, we prove that the probability of separability increases as the translation increases. Thus, we conclude that if points are drawn equiprobably from densities fo(x) and f1(x) = fo(x + tw) then the probability of linear separability is minimum at t = 0 and increases with t for t > 0.     

On the complexity of one-shot translational separability

The problem of deciding whether 2- or 3-dimensional objects can be separated by a sequence of arbitrary translational motions is known to have exponential lower bounds. However, under certain restrictions on the type of motions, polynomial time bounds have been shown. An example is finding a subset of the parts that is removable by a single translation. In this case, the main restriction is that all selected parts are required to be removed in the same direction and with the same velocity. It was an open question whether the polynomial time bound can be achieved if more than a single velocity is allowed for the moving parts. In this paper, we answer this question by proving that such ‘multi-handed’ separability problems are NP-hard.     

Solving the irregular strip packing problem via guided local search for overlap minimization

The irregular strip-packing problem (ISP) requires a given set of non-convex polygons to be placed without overlap within a rectangular container having a fixed width and a variable length, which is to be minimized. As a core sub-problem to solve ISP, we consider an overlap minimization problem (OMP) whose objective is to place all polygons into a container with given width and length so that the total amount of overlap between polygons is made as small as possible. We propose to use directional penetration depths to measure the amount of overlap between a pair of polygons, and present an efficient algorithm to find a position with the minimum overlap for each polygon when it is translated in a specified direction. Based on this, we develop a local search algorithm for OMP that translates a polygon in horizontal and vertical directions alternately. Then we incorporate it in our algorithm for OMP, which is a variant of the guided local search algorithm. Computational results show that our algorithm improves the best-known values of some well-known benchmark instances.     

Stabbing c-oriented polygons

Given a point and a set of objects in 2-space, the point's stabbing number is the number of objects in the set enclosing it. We introduce the notion of c-oriented objects, that is, objects whose edges are oriented in only a constant number of previously defined directions. We devise time-optimal algorithms for determining the stabbing numbers of points with respect to a set of c-oriented polygons: Given a mixed set of points and polygons of size n we show how to determine the stabbing numbers of all points in O(n log n) time. For a static set of polygons we are able to answer stabbing number queries in O(log n) time. For the second problem the same time bound was achieved previously, but only with much higher space- and preprocessing-costs.     

基于量子态系数矩阵的纠缠判定准则

量子纠缠的判定问题（也称为可分性判定问题）是量子纠缠理论中的核心问题之一。越来越多的两体纠缠判定准则被提出,但其中大部分都难以理解和计算,或是难以应用到任意多体量子系统中。为此,对于一个任意的多体量子纯态,基于其系数矩阵提出了一个纠缠判定准则。通过考察一个量子态的系数矩阵的秩,就可以断定该状态是可分态还是纠缠态。通过具体的实例表明,所提出的方法可以找到一个多体量子态的具体可分形式,并且简单易懂、方便计算。     

A simple linear hidden-line algorithm for star-shaped polygons

A very simple, linear-running-time algorithm is presented for solving the hidden-line problem for star-shaped polygons. The algorithm first decomposes the visibility regions into edge-visible polygons and then solves the hidden-line problem for these simpler polygons. In addition to simplicity the algorithm possesses the virtue of affording a very easy proof of correctness. Some applications where this problem arises are mentioned.     

Solving visibility and separability problems on a mesh-of-processors

In this paper we study parallel algorithms for the Mesh-of-Processors architecture to solve visibility and related separability problems for sets of simple polygons in the plane. In particular, we present the following algorithms:

- AnO( \(\sqrt N\) time algorithm for computing on a Mesh-of-Processors of size N the visibility polygon from a point located in anN-vertex polygon, possibly with holes.

-O( \(\sqrt N\) ) time algorithms for computing on a Mesh-of-Processors of sizeN the set of all points on the boundary of anN-vertex polygonP which are visible in a given directiond as well as the visibility hull ofP for a given directiond.

- AnO( \(\sqrt N\) ) time algorithm for detecting on a Mesh-of-Processors of size 2N whether twoN-vertex polygons are separable in a given direction and anO( \(\sqrt {MN}\) ) time algorithm for detecting on a Mesh-of-Processors of sizeMN whetherM N-vertex polygons are sequentially separable in a given direction.

All proposed algorithms are asymptotically optimal (for the Mesh-of-Processors) with respect to time and number of processors.     

Translational polygon containment and minimal enclosure using mathematical programming

A new algorithm is given for the two-dimensional translational containment problem: find translations for k polygons which place them inside a polygonal container without overlapping. Both the polygons and the container can be non-convex. The algorithm is based on mathematical programming principles. The containment algorithm is generalized to solve minimal enclosure problems: find the minimal area enclosing square or minimal area enclosing rectangle for k translating polygons. The containment algorithm consists of new algorithms for restriction , evaluation , and subdivision of two-dimensional configuration spaces. Restriction establishes lower bounds through relaxation and the solution of linear programs. Evaluation establishes upper bounds by finding potential solutions. Subdivision branches, when necessary, by introducing a cutting plane. The algorithm shows that either the upper bound of the objective (overlap) is exactly zero or the lower bound is greater than zero. Hence, it gives an exact solution to the containment problem. Experiments show that new containment algorithm clearly outperforms purely geometric containment algorithms. For data sets from the apparel industry, it can solve containment for up to ten non-convex polygons in practice. An implementation of the algorithm given in this paper has been licensed by Gerber Garment Technologies, the largest provider of textile CAD/CAM software in the US, and they are incorporating it into an existing CAD/CAM software product.     

Polygon-based post-process motion blur

This paper discusses a three-pass raster motion-blur algorithm (and some generalizations) in the context of texture-mapped polygons and its application to blurring objects and surfaces made up of multiple polygons, which may move in different directions.     

Assembly sequences for polyhedra

The problem of finding sequences of motions for the assembly of a given object consisting of polyhedral parts arises in assembly planning. We describe an algorithm to compute the set of all translations separating two polyhedra withn vertices inO(n⁴) steps and show that this is optimal. Given an assembly ofk polyhedra with a total ofn vertices, an extension of this algorithm identifies a valid translation and removable subassembly inO(k²n⁴) steps if one exists. Based on the second algorithm, a polynomial-time method for finding a complete assembly sequence consisting of single translations is derived. An implementation incorporates several changes to achieve better average-case performance; experimental results obtained for simple assemblies are described.This research was funded by DARPA Contract N00014-88-K-0620 (Office of Naval Research) and the Stanford Integrated Manufacturing Association (SIMA).     

基于凸包求解的简单多边形方向判断新算法

Graham ScanA求解简单多边形凸包算法简洁高效,但是对于未确定方向的简单多边形,该算法需设定一个方向求解其凸包。提出一种新的算法,该算法通过利用凸包求解的Graham ScanA算法来判断简单多边形的方向。算法取得了较好的实用效果。     

判定凸多边形可碰撞的最优算法

设P与Q是平面内任意二互不相交的凸多边形,d为任一给定方向,本文研究P沿d以平移方式运动可否与Q碰撞的判定问题.文中定义了凸多边形顶点集上的偏序关系,给出了判定可碰撞性的新的充分必要条件,据此采用四分搜索方法构造了判定可碰撞的算法.在最坏情况下算法的复杂度为O(logn),在不计常数因子的情况下,这是最优的.     

Using extended feature objects for partial similarity retrieval

In this paper, we introduce the concept of extended feature objects for similarity retrieval. Conventional approaches for similarity search in databases map each object in the database to a point in some high-dimensional feature space and define similarity as some distance measure in this space. For many similarity search problems, this feature-based approach is not sufficient. When retrieving partially similar polygons, for example, the search cannot be restricted to edge sequences, since similar polygon sections may start and end anywhere on the edges of the polygons. In general, inherently continuous problems such as the partial similarity search cannot be solved by using point objects in feature space. In our solution, we therefore introduce extended feature objects consisting of an infinite set of feature points. For an efficient storage and retrieval of the extended feature objects, we determine the minimal bounding boxes of the feature objects in multidimensional space and store these boxes using a spatial access structure. In our concrete polygon problem, sets of polygon sections are mapped to 2D feature objects in high-dimensional space which are then approximated by minimal bounding boxes and stored in an R-tree. The selectivity of the index is improved by using an adaptive decomposition of very large feature objects and a dynamic joining of small feature objects. For the polygon problem, translation, rotation, and scaling invariance is achieved by using the Fourier-transformed curvature of the normalized polygon sections. In contrast to vertex-based algorithms, our algorithm guarantees that no false dismissals may occur and additionally provides fast search times for realistic database sizes. We evaluate our method using real polygon data of a supplier for the car manufacturing industry. Edited by R. Güting. Received October 7, 1996 / Accepted March 28, 1997     

Globally convergent decomposition methods for nonconvex optimization problems

In this paper we consider nonlinear optimization problems of a separable form with nonconvex objective and convex constraints. A convexification procedure preserving separability is given in order that primal-dual methods are applicable. A globally convergent algorithm observing computational aspects is given. This algorithm was applied to a real world problem with 1007 variables and 4030 constraints for controlling the heads of a hydroenergy power station.     

多边形的方向与圆弧可视性

本文继Ｅｌ－Ｇｉｎｄｙ与Ａｖｉｓ（１９８１），Ａｖｉｓ与Ｔｏｕｓｓａｉｎｔ（１９８１），Ｌｅｅ与Ｌｉｎ（１９８６）及Ｓａｃｋ与Ｓｕｒｉ（１９９０）提出并讨论图一菜的点可视性与线段可视性之后，提出了图形的方向与圆弧可视性概念，给出了计算简单多边形的方向可视集与中视集的最优算法，本文所得结果可应用于与图形运动有关的机器人学，计算机图形学和ＣＡＭ与ＶＬＳＩ设计中。     

Extremum Problems with Separable Graphs

The paper introduces a geometric feature of separability of graphs for extremum equality-type boundary problems. To find an optimal value for a problem with an almost separable graph, the paper presents an iteration algorithm, each step of which minimizes Lagrangian function for the main variable with a fixed Lagrangian multiplier. This algorithm dates back to Krasovskii extremal shift method from differential game theory.     

Recursive Partitioning Technique for Combining Multiple Classifiers

Various methods of reducing correlation between classifiers in a multiple classifier framework have been attempted. Here we propose a recursive partitioning technique for analysing feature space of multiple classifier decisions. Spectral summation of individual pattern components in intermediate feature space enables each training pattern to be rated according to its contribution to separability, measured as k-monotonic constraints. A constructive algorithm sequentially extracts maximally separable subsets of patterns, from which is derived an inconsistently classified set (ICS). Leaving out random subsets of ICS patterns from individual (base) classifier training sets is shown to improve performance of the combined classifiers. For experiments reported here on artificial and real data, the constituent classifiers are identical single hidden layer MLPs with fixed parameters.     

Polyhedral representation of fuzzy linear bases

 In [15], we introduced the concepts of fuzzy bases, fuzzy linear interpolation and fuzzy polygon of four-component fuzzy linear bases. In [16], these concepts were used in the maximal profile of the set of polygons generated from a set of break points for each variable dimension. Theconcept was operationalized in a fuzzy linear basis algorithm (FLBA) for nonlinear separable programming problems involving no more than a finite number of discontinuities. The FLBA provides a powerful platform forparallel processing of the fuzzy linear sub-problems included in the finite FLB-chain. In this paper we extend the theory of fuzzy linear bases from the set of polygons toapolyhedral representation of four-component fuzzy linear bases defined on a closed subset of the real line.     

Boolean Operations on Conic Polygons

An algorithm for Boolean operations on conic polygons is proposed.Conic polygons are polygons consisting of conic segments or bounded conics with directions.Preliminaries of Boolean operations on general polygons are presented.In our algorithm,the intersection points and the topological relationships between two conic polygons are computed.Boundaries are obtained by tracking path and selecting uncrossed boundaries following rule tables to build resulting conic polygons. We define a set of rules for the i...