The Digital Topology of Sets of Convex Voxels

Classical digital geometry deals with sets of cubical voxels (or square pixels) that can share faces, edges, or vertices, but basic parts of digital geometry can be generalized to sets S of convex voxels (or pixels) that can have arbitrary intersections. In particular, it can be shown that if each voxel P of S has only finitely many neighbors (voxels of S that intersect P), and if any nonempty intersection of neighbors of P intersects P, then the neighborhood N(P) of every voxel P is simply connected and without cavities, and if the topology of N(P) does not change when P is deleted (i.e., P is a “simple” voxel), then deletion of P does not change the topology of S.     

Lower bounds on the rotation distance of binary trees

The rotation distanced(S,T) between two binary trees S, T of n vertices is the minimum number of rotations to transform S into T. While it is known that d(S,T)?2n−6, a well-known conjecture states that there are trees for which this bound is sharp for any value of n?11. We are unable to prove the conjecture, but we give here some simple criteria for lower bound evaluation, leading for example to individuate some “regular” tree structures for which d(S,T)=3n/2−O(1), or d(S,T)=5n/3−O(1).     

Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

Let Wn denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Qn, and let S and T be any two sets of k vertices in different partite sets of Wn. In this paper, we show that the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn if and only if k=²n−1 or the graph Wn−(S∪T) has a perfect matching. Moreover, if the graph Wn−(S∪T) has a perfect matching M, then the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn and all edges in M. And some corollaries are given.     

Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons

Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most times the optimum, Δ being the maximum degree of the input network. This is best-possible if and if the processors are required to run in polynomial-time. We then show how to construct dominating sets that have the above properties, as well as the “low stretch” property that any two adjacent nodes in the network have their dominators at a distance of at most in the output network. (Given a dominating set S, a dominator of a vertex u is any v∈S such that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal.     

Transforming spanning trees and pseudo-triangulations

Let TS be the set of all crossing-free straight line spanning trees of a planar n-point set S. Consider the graph TS where two members T and T^′ of TS are adjacent if T intersects T^′ only in points of S or in common edges. We prove that the diameter of TS is O(logk), where k denotes the number of convex layers of S. Based on this result, we show that the flip graph PS of pseudo-triangulations of S (where two pseudo-triangulations are adjacent if they differ in exactly one edge—either by replacement or by removal) has a diameter of O(nlogk). This sharpens a known O(nlogn) bound. Let be the induced subgraph of pointed pseudo-triangulations of PS. We present an example showing that the distance between two nodes in is strictly larger than the distance between the corresponding nodes in PS.     

A REVIEW OF TREE CONVEX SETS TEST

A collection of sets may have some interesting properties which help identify efficient algorithms for constraint satisfaction problems and combinatorial auction problems. One of the properties is tree convexity. A collection S of sets is tree convex if we can find a tree T whose nodes are the union of the sets of S and each set of S is the nodes of a subtree of T . This concept extends that of row convex sets each of which is an interval over a total ordering of the elements of the union of these sets. An interesting problem is to find efficient algorithms to test whether a collection of sets is tree convex. It is not known before if there exists a linear time algorithm for this test. In this paper, we review the materials that are the key to a linear algorithm: hypergraphs, a characterization of tree convex sets and the acyclic hypergraph test algorithm. Some typos in the original paper of the acyclicity test are corrected here. Some experiments show that the linear algorithm is significantly faster than a well‐known existing algorithm.     

Lucky labelings of graphs

Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by η(G).Using algebraic methods we prove that η(G)?k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that η(T)?2 for every tree T, and η(G)?3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that for every planar graph G. Nevertheless we offer a provocative conjecture that η(G)?χ(G) for every graph G.     

A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.     

An improved algorithm for the red-blue hitting set problem with the consecutive ones property

Let S be a set of elements. We say that a collection C of subsets of S has the consecutive ones property if there exist a linear order on S and a 0-1 matrix M, where Mij=1 if and only if the jth element is in the ith set in C, such that all 1's appear consecutively in each row of M. A set X∈C is hit by a subset S^′⊆S if X∩S^′≠∅. Let Cr (red collection) and Cb (blue collection) be two collections of subsets of S respectively. The red-blue hitting set problem asks for a subset S^′⊆S such that all sets in the blue collection are hit by S^′, while the number of sets in the red collection hit by S^′ has to be minimum. We present a shortest-path based algorithm with time complexity O(|Cb||S|+|Cr||S|+²|S|) for this problem with Cr∪Cb having the consecutive ones property, which improves the previous time bound O(|Cr||Cb|²|S|) by Dom et al. (2008) [8].     

Generalized fuzzy rough sets determined by a triangular norm

The theory of rough sets has become well established as an approach for uncertainty management in a wide variety of applications. Various fuzzy generalizations of rough approximations have been made over the years. This paper presents a general framework for the study of T-fuzzy rough approximation operators in which both the constructive and axiomatic approaches are used. By using a pair of dual triangular norms in the constructive approach, some definitions of the upper and lower approximation operators of fuzzy sets are proposed and analyzed by means of arbitrary fuzzy relations. The connections between special fuzzy relations and the T-upper and T-lower approximation operators of fuzzy sets are also examined. In the axiomatic approach, an operator-oriented characterization of rough sets is proposed, that is, T-fuzzy approximation operators are defined by axioms. Different axiom sets of T-upper and T-lower fuzzy set-theoretic operators guarantee the existence of different types of fuzzy relations producing the same operators. The independence of axioms characterizing the T-fuzzy rough approximation operators is examined. Then the minimal sets of axioms for the characterization of the T-fuzzy approximation operators are presented. Based on information theory, the entropy of the generalized fuzzy approximation space, which is similar to Shannon’s entropy, is formulated. To measure uncertainty in T-generalized fuzzy rough sets, a notion of fuzziness is introduced. Some basic properties of this measure are examined. For a special triangular norm T = min, it is proved that the measure of fuzziness of the generalized fuzzy rough set is equal to zero if and only if the set is crisp and definable.     

On the complexity of finding balanced oneway cuts

A bisection of an n-vertex graph is a partition of its vertices into two sets S and T, each of size n/2. The bisection cost is the number of edges connecting the two sets. In directed graphs, the cost is the number of arcs going from S to T. Finding a minimum cost bisection is NP-hard for both undirected and directed graphs. For the undirected case, an approximation of ratio O(log²n) is known. We show that directed minimum bisection is not approximable at all. More specifically, we show that it is NP-hard to tell whether there exists a directed bisection of cost 0, which we call oneway bisection. In addition, we study the complexity of the problem when some slackness in the size of S is allowed, namely, (1/2−ε)n?|S|?(1/2+ε)n. We show that the problem is solvable in polynomial time when , and provide evidence that the problem is not solvable in polynomial time when ε=o(1/(logn)⁴).     

A simple proof of Rosenfeld's characterization of digital straight line segments

A digital straight line segment is defined as the grid-intersect quantization of a straight line segment in the plane. Let S be a set of pixels on a square grid. Rosenfeld [8] showed that S is a digital straight line segment if and only if it is a Digital arc having the chord property. Then Kim and Rosenfeld [3,6] showed that S has the chord properly if and if for every p, q?S there is a digital straight line segment C ? S such that p and q are the extremities of C.We give a simple proof of these two results based on the Transversal Theorem of Santaló. We show how the underlying methodology can be generalized to the case of (infinite) digital straight lines and to the quantization of hyperplanes in an n-dimensional space for n ≥ 3.     

Applications of interval valued t-norms (t-conorms) to fuzzy n-ary sub-hypergroups

In this paper, we study a generalization of group, hypergroup and n-ary group. Firstly, we define interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup with respect to a t-norm T (t-conorm S). We give a necessary and sufficient condition for, an interval-valued fuzzy subset to be an interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup with respect to a t-norm T (t-conorm S). Secondly, using the notion of image (anti image) and inverse image of a homomorphism, some new properties of interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup are obtained with respect to infinitely ∨-distributive t-norms T (∧-distributive t-conorms S). Also, we obtain some results of T-product (S-product) of the interval-valued fuzzy subsets for infinitely ∨-distributive t-norms T (∧-distributive t-conorms S). Lastly, we investigate some properties of interval-valued fuzzy subsets of the fundamental n-ary group with infinitely ∨-distributive t-norms T (∧-distributive t-conorms S).     

Listing closed sets of strongly accessible set systems with applications to data mining

We study the problem of listing all closed sets of a closure operator σ that is a partial function on the power set of some finite ground set E, i.e., σ:F→F with F⊆P(E). A very simple divide-and-conquer algorithm is analyzed that correctly solves this problem if and only if the domain of the closure operator is a strongly accessible set system. Strong accessibility is a strict relaxation of greedoids as well as of independence systems. This algorithm turns out to have delay O(|E|(T_F+T_σ+|E|)) and space O(|E|+S_F+S_σ), where T_F, S_F, T_σ, and S_σ are the time and space complexities of checking membership in F and computing σ, respectively. In contrast, we show that the problem becomes intractable for accessible set systems. We relate our results to the data mining problem of listing all support-closed patterns of a dataset and show that there is a corresponding closure operator for all datasets if and only if the set system satisfies a certain confluence property.     

Detecting moving objects from a video taken by a moving camera using sequential inference of background images

This paper proposes a method of detecting moving objects using sequential inference of the background in a video taken with a moving camera. In the video taken using a moving camera, all positions of pixels change every frame. The positions of the background pixels in the image frame T are not the same as the positions of the background pixels in the image frame T + 1. 2D projective transform can be used to find changes in the pixel position every frame. Bilinear interpolation with four nearest pixels around the pixel in image frame T which corresponds to a pixel in the image frame T+1 can be used for creating a background model at T + 1. Having obtained the background model, a pixel in image frame T + 1 can be determined if it is a background pixel or a foreground pixel. The detection results of the proposed method are compared with the ground truth to determine the effectiveness of the proposed method.     

Representing Hyper-arithmetical Sets by Equations over Sets of Integers

Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition, defined as S+T={m+n?Om??S,n??T}, and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \mathop {\mbox {$-^{\hspace {-.5em}\cdot }\,\,$}}T=\{m-n \mid m \in S, n \in T, m \geq n\}$ . Testing whether a given system has a solution is $\varSigma ^{1}_{1}$ -complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.     

Atanassov’s intuitionistic fuzzy submodules with respect to a t-norm

In this paper, t-norm based intuitionistic fuzzy submodules are defined, and their various properties are investigated. We also show that if an intuitionistic fuzzy set of a module is an intuitionistic fuzzy submodule with respect to a t-norm, then it is also an intuitionistic fuzzy submodule with respect to the annihilation t-norm. We investigate the nature of intuitionistic fuzzy submodules of a module with the help of their respective cut sets. We obtain some results based on (α, β)-level sets and t-norm based α-cut sets of an intuitionistic fuzzy submodule with respect to a t-norm T.     

A note on ‘geometric transforms’ of digital sets

We define a ‘geometric transform’ on the digital plane as a function ? that takes pairs (P, S), where S is a set and P a point of S, into nonnegative integers, and where $\text{?(S, P)}$ depends only on the positions of the points of S relative to P. Transforms of this type are useful for segmenting and describing S. Two examples are ‘distance transforms’, for which $\text{?(S, P)}$ is the distance from P to S, and ‘isovist transforms’, where $\text{?(S, P)}$, is the area of the part S visible from P. This note characterizes geometric transforms that have certain simple set-theoretic properties, e.g., such that $\text{?(S?T,P) = ?(S,P)∧?(T,P)}$ for all S, T, P. It is shown that a geometric transform has this intersection property if and only if it is defined in a special way in terms of a ‘neighborhood base’; the class of such ‘neighborhood transforms’ is a generalization of the class of distance transforms.     

High convergence rates of digital image transformation by numerical integration using spline functions

This paper introduces an intriguing topic in image processing where accuracy of images even in details is important and adopts an intriguing methodology dealing with discrete topics by continuous mathematics and numerical approximation. The key idea is that a pixel of images at different levels can be quantified by a greyness value, which can then be regarded as the mean of an integral of continuous functions over a certain region, and evaluated by numerical integration approximately. However, contrasted to the traditional integration, the integrand has different smooth nature in different subregions due to piecewise interpolation and approximation. New treatments of approximate integration and new discrete algorithms of images have been developed.The cycle conversion T⁻¹T of image transformations is said if an image is distorted by a transformation T and then restored back to itself by the inverse transformation T⁻¹. Combined algorithms of discrete techniques proposed in [1–3] only have the convergence rates O(1/N) and O(1/N²) of sequential greyness errors, where N is the division number for a pixel split into N² subpixels. This paper reports new combination algorithms using spline functions to achieve the high convergence rates O(1/N³) and O(1/N⁴) of digital image transformations under the cycle conversion. Both error analysis and numerical experiments have been provided to verify the high convergence rates. High convergence rates of discrete algorithms are important in saving CPU time, particularly to multi-greyness images. Moreover, the computational figures for real images of 256 × 256 with 256 greyness levels, in which N = 2 is good enough for practical requirements, display validity, and effectiveness of the new algorithms in this paper.     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.