Solving Some Discrepancy Problems in NC

We show that several discrepancy-like problems can be solved in NC nearly achieving the discrepancies guaranteed by a probabilistic analysis and achievable sequentially. For example, we describe an NC algorithm that given a set system (X, S) , where X is a ground set and S⊆2 ^X , computes a set R⊆X so that for each S∈ S the discrepancy ||R S|-|R^-∩S|| is . Whereas previous NC algorithms could only achieve discrepancies with ɛ>0 , ours matches the probabilistic bound within a multiplicative factor 1+o(1) . Other problems whose NC solution we improve are lattice approximation, ɛ -approximations of range spaces with constant VC-exponent, sampling in geometric configuration spaces, approximation of integer linear programs, and edge coloring of graphs. Received June 26, 1998; revised February 18, 1999.     

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations

The combinatorial complexities of (1) the Voronoi diagram of moving points in 2D and (2) the Voronoi diagram of lines in 3D, both under the Euclidean metric, continues to challenge geometers because of the open gap between the Ω(n²) lower bound and the O(n3+?) upper bound. Each of these two combinatorial problems has a closely related problem involving Minkowski sums: (1′) the complexity of a Minkowski sum of a planar disk with a set of lines in 3D and (2′) the complexity of a Minkowski sum of a sphere with a set of lines in 3D. These Minkowski sums can be considered “cross-sections” of the corresponding Voronoi diagrams. Of the four complexity problems mentioned, problems (1′) and (2′) have recently been shown to have a nearly tight bound: both complexities are O(n2+?) with lower bound Ω(n²).In this paper, we determine the combinatorial complexities of these four problems for some very simple input configurations. In particular, we study point configurations with just two degrees of freedom (DOFs), exploring both the Voronoi diagrams and the corresponding Minkowski sums. We consider the traditional versions of these problems to have 4 DOFs. We show that even for these simple configurations the combinatorial complexities have upper bounds of either O(n²) or O(n2+?) and lower bounds of Ω(n²).     

An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.     

Non-commutative morphology: Shapes, filters, and convolutions

Group morphology is a generalization of mathematical morphology which makes an explicit distinction between shapes and filters. Shapes are modeled as point sets, for example binary images or 3D solid objects, while filters are collections of transformations (such as translations, rotations or scalings). The action of a filter on a shape generalizes the basic morphological operations of dilation and erosion. This shift in perspective allows us to compose filters independent of shapes, and leads to a non-commutative generalization of the Minkowski sum and difference which we call the Minkowski product and quotient respectively. We show that these operators are useful for unifying, formulating and solving a number of important problems, including translational and rotational configuration space problems, mechanism workspace computation, and symmetry detection. To compute these new operators, we propose the use of group convolution algebras, which extend classical convolution and the Fourier transform to non-commutative groups. In particular, we show that all Minkowski product and quotient operations may be represented implicitly as sublevel sets of the same real-valued convolution function.     

Global state and feedback equivalence of nonlinear systems

The problem of finding global state space transformations and global feedback of the form u(t)= α(x) + ν(t) to transform a given nonlinear system to a controllable linear system on Rⁿ or on an open subset of Rⁿ, is considered here. We give a complete set of differential geometric conditions which are equivalent to the existence of a solution to the above problem.     

Fast and robust retrieval of Minkowski sums of rotating convex polyhedra in 3-space

We present a novel method for fast retrieval of exact Minkowski sums of pairs of convex polytopes in R³, where one of the polytopes frequently rotates. The algorithm is based on pre-computing a so-called criticality map, which records the changes in the underlying graph structure of the Minkowski sum of the two polytopes, while one of them rotates. We give tight combinatorial bounds on the complexity of the criticality map when the rotating polytope rotates about one, two, or three axes. The criticality map can be rather large already for rotations about one axis, even for summand polytopes with a moderate number of vertices each. We therefore focus on the restricted case of rotations about a single, though arbitrary, axis.Our work targets applications that require exact collision detection such as motion planning with narrow corridors and assembly maintenance where high accuracy is required. Our implementation handles all degeneracies and produces exact results. It efficiently handles the algebra of exact rotations about an arbitrary axis in R³, and it well balances between preprocessing time and space on the one hand, and query time on the other.We use Cgal arrangements and in particular the support for spherical Gaussian maps to efficiently compute the exact Minkowski sum of two polytopes. We conducted several experiments (i) to verify the correctness of the algorithm and its implementation, and (ii) to compare its efficiency with an alternative (static) exact method. The results are reported.     

A fast algorithm for Steiner trees

Summary Given an undirected distance graph G=(V, E, d) and a set S, where V is the set of vertices in G, E is the set of edges in G, d is a distance function which maps E into the set of nonnegative numbers and SV is a subset of the vertices of V, the Steiner tree problem is to find a tree of G that spans S with minimal total distance on its edges. In this paper, we analyze a heuristic algorithm for the Steiner tree problem. The heuristic algorithm has a worst case time complexity of O(¦S¦¦V¦ ²) on a random access computer and it guarantees to output a tree that spans S with total distance on its edges no more than 2(1–1/l) times that of the optimal tree, where l is the number of leaves in the optimal tree.     

Fuzzy implication can be arbitrarily complicated: A theorem

In fuzzy logic, there are several methods of representing implication in terms of &, ∨, and ¬; in particular, explicit representations define a class of S implications, implicit representations define a class of R implications. Some reasonable implication operations have been proposed, such as Yager's a^b, that are difficult to represent as S or R implications. For such operations, a new class of representations has recently been proposed, called A implications, for which the relationship between implications and the basic operations &, ∨, and ¬ is even more complicated. A natural question is: Is this complexity really necessary? In other words, is it true that A operations cannot be described as S or R operations, or they can, but we simply have not found these representations? In this paper we show that yes, the complexity is necessary, because there are operations that cannot be represented in a simpler form. © 1998 John Wiley & Sons, Inc.     

A solution of polygon containment,spatial planning,and other related problems using Minkowski operations

This paper gives a complete solution to the polygon containment problem under translation and other related problems for all kinds of two dimensional regions. The solution is achieved in three steps. First, it is shown that the containment and the related problems can be directly mapped to Minkowski decomposition and addition problems. Minkowski decomposition, which is intrinsically a geometric problem, is then reformulated in terms of set operations and set theoretic tools are used to reduce the computational complexity of the problem. Finally, a new technique, termed asdecomposition boundary tracing technique, is devised and employed for the solution of the decomposition problem. This new technique brings out aunified algorithmic approach to solve all kinds of decomposition problems in a two dimensional space, and thereby the containment problem in its entirety.     

A faster approximation algorithm for the Steiner problem in graphs

Summary We present an algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The set V-S is traditionally denoted as Steiner vertices. The total distance on all edges of this Steiner tree is at most 2(1–1/l) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(¦E¦log¦V¦) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph. It improves dramatically on the best previously known bound of O(¦S¦¦V¦²), unless the graph is very dense and most vertices are Steiner vertices. The essence of our algorithm is to find a generalized minimum spanning tree of a graph in one coherent phase as opposed to the previous multiple steps approach.The work of this author was partially supported by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. This work was performed while this author was a summer visitor at the IBM T.J. Watson Research Center.On leave from: Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6380, D-7500 Karlsruhe, Federal Republic of Germany     

Relative blending

Solid models may be blended through filleting or rounding operations that typically replace the vicinity of concave or convex edges by blends that smoothly connect to the rest of the solid’s boundary. Circular blends, which are popular in manufacturing, are each the subset of a canal surface that bounds the region swept by a ball of constant or varying radius as it rolls on the solid while maintaining two tangential contacts. We propose to use a second solid to control the radius variation. This new formulation supports global blending (simultaneous rounding and filleting) operations and yields a simple set-theoretic formulation of the relative blending R_B(A) of a solid A given a control solid B. We propose user-interface options, describe practical implementations, and show results in 2 and 3 dimensions.     

Voxelized Minkowski sum computation on the GPU with robust culling

We present a new approach for computing the voxelized Minkowski sum (excluding any enclosed voids) of two polyhedral objects using programmable Graphics Processing Units (GPUs). We first cull out surface primitives that will not contribute to the final boundary of the Minkowski sum, analyzing and adaptively bounding the rounding errors of the culling algorithm to solve the floating point error problem. The remaining surface primitives are then rendered to depth textures along six orthogonal directions to generate an initial solid voxelization of the Minkowski sum. Finally we employ fast flood fill to find all the outside voxels. We generate both solid and surface voxelizations of Minkowski sums without enclosed voids and support high volumetric resolution of 1024³ with low video memory cost. The whole algorithm runs on the GPU and is at least one order of magnitude faster than existing boundary representation (B-rep) based algorithms. It avoids the large number of 3D Boolean operations needed in most existing algorithms and is easy to implement. The voxelized Minkowski sums can be used in a variety of applications including motion planning and penetration depth computation.     

An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases

After a relation scheme R is decomposed into the set of schemes ρ={R1，…，Rn},we may pose queries as if Rexisted in the database,taking a join of Ri‘s,when it is necessary to implement the query,Suppos a query involves a set of attributes S R，we want to find the smallest subset of ρ whose union includes.S.We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm.A subset of ρ whose union includes S and has a decomposition into 3NF with a lossless join and preservation of dependencies in given in the paper.     

Solving Connected Dominating Set Faster than 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves. Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2 ⁿ ) algorithm that enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such a difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly. In this paper we break the 2 ⁿ barrier, by presenting a simple O(1.9407 ⁿ ) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique. An extended abstract of this paper appeared in the proceedings of FSTTCS’06. Fedor V. Fomin was additionally supported by the Research Council of Norway.     

Logical Methods for Studying Relations in Criterial Spaces with Arbitrary Ordinal Scales

Proposed was an approach enabling one to reduce studies of the properties of ordinal relations for criteria with an arbitrary (including finite) set of values to similar problems for relations defined over the entire n-dimensional real space R ⁿ. It enabled one to prove that all main findings, methods, and algorithms obtained previously for the ordinal relations on R ⁿ can be extended in arbitrary criterial spaces to the ordinal relations with the criterion scale cardinalities not less than three.     

Note on the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e., a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G₁(V,E₁), G₂(V,E₂), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph GS(V,ES), E₁⊆ES⊆E₂, which has a homogeneous set. Recently, Tang et al. [Inform. Process. Lett. 77 (2001) 17-22] proposed an interesting O(_?1⋅n²) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm by presenting three counterexamples.     

Minkowski sums of point sets defined by inequalities

The existing approaches support Minkowski sums for the boundary, set-theoretic, and ray representations of solids. In this paper, we consider the Minkowski sum operation in the context of geometric modeling using real functions. The problem is to find a real function f₃(X) for the Minkowski sum of two objects defined by the inequalities f₁(X) ≥ 0 and f₂(X) ≥ 0. We represent the Minkowski sum as a composition of other operations: the Cartesian product, resulting in a higher-dimensional object, and a mapping to the original space. The Cartesian product is realized as an intersection in the higher-dimensional space, using an R-function. The mapping projects the resulting object along n coordinate axes, where n is the dimension of the original space. We discuss the properties of the resulting function and the problems of analytic and numeric implementation, especially for the projection operation. Finally, we apply Minkowski sums to implement offsetting and metamorphosis between set-theoretic solids with curvilinear boundaries.     

Tool allocation in flexible manufacturing systems with tool alternatives

In this paper, a heuristic approach for tool selection in flexible manufacturing systems (FMS) is presented. The proposed approach utilizes the ratio of tool life over tool size (L/S) for tool selection and allocation. The proposed method selects tool types with high L/S ratios by considering tool alternatives for the operations assigned to each machine. The performance of the method is demonstrated in sample problems as static examples, as well as in a simulation study for further analysis. This study also presents a survey of several approaches related to loading and tool allocation problems in FMS, highlights the importance of tooling, and discusses the practical aspects of tool-oriented decision-making. An extended framework, which expands on the L/S concept, is also presented.     

A review of: “CYBERNETICS: THEORY AND APPLICATIONS”, by Robert Trappl,Hemisphere, Washington,D.C., 1983. $80, xii + 455 pages.

The greatest portion of papers dealing with the Dempster-Shafer theory consider the case when the basic universe is a finite set, so that all the numerical characteristics introduced and investigated in the D-S theory, including the believeability and plausibility functions as the most important ones, can be easily defined by well-known combinatoric formulas outgoing from a simple probability distribution (basic belief assignment, in the terms of D-S theory) on the power-set 𝒫(S) of all subsets of S. The obvious fact that these numerical characteristics can be equivalently defined also by appropriate set-valued random variables becomes to be of greater importance in the case when S is infinite. We investigate, in this paper, the case when the power-set 𝒫(S) over an infinite set S is equipped by a nonempty σ-field  ? 𝒫(𝒫(S)) andwhen the belief and plausibility functions are defined by a set-valued random variable (i.e., -measurable mapping) which takes a given probability space into the measurable space (𝒫(S),) In general, the values of the two functions in question need not be defined for each subset T of S. Therefore, we define four extensions of these functions to whole the (S) based on the well-known concepts of inner and outer measure, and investigate their properties; interesting enough, just one of them respect the philosophy of the D-S approach to uncertainty quantification and processing and keeps the properties possessed by believeability and plausibility functions defined over finite spaces.