Winding and Euler numbers for 2D and 3D digital images

New algorithms for computing the Euler number of a 3D digital image S are given, based on smoothing the image to a differentiable object and applying theorems of differential geometry and algebraic topology. They run in O(n) time, where n is the number of object elements of S with neighbors not in S. The basic idea is general and easily extended to images defined by other means, such as a hierarchical data structure or a union of isothetic (hyper) rectangles.     

Two simply connected sets that have the same area are IP-equivalent

A pair of neighboring, opposite-valued pixels in a two-valued digital image is called interchangeable if reversing their values preserves the topology of the image. It was conjectured in Rosenfeld, Saha, Nakamula, Pattern Recognition 34 (2001) 1853-1865 that if two digital images have the same number of 1's, and their sets of 1's S,T are simply connected, then S can be transformed into T by a sequence of interchanges. In that paper this conjecture was proved only for certain special cases—for example, if S and T are arcs. This paper proves the conjecture for arbitrary simply connected sets.     

‘Continuous’ functions on digital pictures

The epsilon-delta definition of continuity has a natural analog for functions that take lattice points into lattice points. It turns out that a function f is ‘continuous’ if and only if it takes neighbors into neighbors, i.e., if Q is a neighbor of P, then f(Q) = f(P) or is a neighbor of f(P) (diagonal neighbors not allowed). Some basic properties of such ‘continuous’ functions are established. In particular, we show that a ‘continuous’ function from a finite block of lattice points into itself has an ‘almost-fixed’ point P such that f(P) is a neighbor of P (diagonal neighbors allowed). We also show that a function is one-to-one and continuous if and only if it is a combination of translations, rotations by multiples of 90°, or reflections in a horizontal, vertical, or diagonal line.     

Approximation Algorithms for Intersection Graphs

We study three complexity parameters that, for each vertex v, are an upper bound for the number of cliques that are sufficient to cover a subset S(v) of its neighbors. We call a graph k-perfectly groupable if S(v) consists of all neighbors, k-simplicial if S(v) consists of the neighbors with a higher number after assigning distinct numbers to all vertices, and k-perfectly orientable if S(v) consists of the endpoints of all outgoing edges from v for an orientation of all edges. These parameters measure in some sense how chordal-like a graph is—the last parameter was not previously considered in literature. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set, minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.     

Topology preservation of template-based 6-subiteration reduction operations

Generally, a reduction operation (e.g., thinning and shrinking) on 3D binary images can be represented as a set of reduction templates where every object voxel of the image satisfying any template is turned to a background voxel. Generally, it is rather difficult, error-prone and time-consuming for verifying the topological soundness of a 3D parallel reduction operation. This paper proposes sufficient conditions of time complexity O(n) for verifying the topological soundness of 3D parallel 6-subiteration reduction operations of n templates where such a kind of 3D reduction operations is performed alternatively from the six orthogonal directions to turn object voxels to background voxels. By such sufficient conditions, the topology soundness of a 3D 6-subiteration parallel reduction operation can be verified by checking each and every of its templates.     

On the diameter of geometric path graphs of points in convex position

For a set S of n points in convex position in the plane, let P(S) denote the set of all plane spanning paths of S. The geometric path graph of S, denoted by Gn, is the graph with P(S) as its vertex set and two vertices P,Q∈P(S) are adjacent if and only if P and Q can be transformed to each other by means of a single edge replacement. Recently, Akl et al. [S.G. Akl, K. Islam, H. Meijer, On planar path transformation, Inform. Process. Lett. 104 (2007) 59-64] showed that the diameter of Gn is at most 2n−5. In this note, we derive the exact diameter of Gn for n?3.     

Axiomatic Digital Topology

The paper presents a new set of axioms of digital topology, which are easily understandable for application developers. They define a class of locally finite (LF) topological spaces. An important property of LF spaces satisfying the axioms is that the neighborhood relation is antisymmetric and transitive. Therefore any connected and non-trivial LF space is isomorphic to an abstract cell complex. The paper demonstrates that in an n-dimensional digital space only those of the (a, b)-adjacencies commonly used in computer imagery have analogs among the LF spaces, in which a and b are different and one of the adjacencies is the “maximal” one, corresponding to 3 ⁿ − 1 neighbors. Even these (a, b)-adjacencies have important limitations and drawbacks. The most important one is that they are applicable only to binary images. The way of easily using LF spaces in computer imagery on standard orthogonal grids containing only pixels or voxels and no cells of lower dimensions is suggested. Vladimir Kovalevsky received his diploma in physics from the Kharkov University (Ukraine) in 1950, the first doctor degree in technical science from the Central Institute of Metrology (Leningrad) in 1957, the second doctor degree in computer science from the Institute of Cybernetics (Kiev) in 1968. Since 1961 he has been the head of Department of Pattern Recognition at that Institute. Lives since 1980 in Germany. Currently he is professor of computer science at the University of Applied sciences Berlin. His research interest include digital geometry, digital topology, computer vision, image processing and pattern recognition.     

Trash removal algorithm for fast construction of the elliptic Gabriel graph using Delaunay triangulation

Given a set of points P, finding near neighbors among the points is an important problem in many applications in CAD/CAM, computer graphics, computational geometry, etc. In this paper, we propose an efficient algorithm for constructing the elliptic Gabriel graph (EGG), which is a generalization of the well-known Gabriel graph and parameterized by a non-negative value α. Our algorithm is based on the observation that a candidate point which may define an edge of an EGG with a given point p∈P is always in the scaled Voronoi region of p with a scale factor 2/α² when the parameter α<1. From this observation, we can reduce the search space for locating neighbors of p in the EGG. For the case of α≥1, due to the fact that EGG is a subgraph of the Delaunay graph of P, EGG can be efficiently computed by watching the validity of each edge in the Delaunay graph. The proposed algorithm is shown to have its time complexity as O(n³) in the worst case and O(n) in the average case when α is moderately close to unity. The idea presented in this paper may similarly apply to other problems for the proximity search for point sets.     

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.     

Analysis of an adaptive algorithm to find the two nearest neighbors

Given a setS ofN distinct elements in random order and a pivotx ∈S, we study the problem of simultaneously finding the left and the right neighbors ofx, i.e.,L=max{u|u<x} andR=min{v|v>x}. We analyze an adaptive algorithm that solves this problem by scanning the setS while maintaining current values for the neighborsL andR. Each new element inspected is compared first against the neighbor in the most populous side, then (if necessary) against the neighbor in the other side, and finally (if necessary), against the pivot. This algorithm may require 3N comparisons in the worst case, but it performs well on the average. If the pivot has rankαN, where α is fixed and <1/2, the algorithm does (1+α)N+Θ(logN) comparisons on the average, with a variance of 3 lnN+Θ(1). However, in the case where the pivot is the median, the average becomes 3/2;N+Θ(√N), while the variance grows to (1/2−π/8)N+Θ(logN). We also prove that, in the αN case, the limit distribution is Gaussian. This work has been supported in part by Grant FONDECYT(Chile) 1950622 and 1981029. Online publication October 6, 2000.     

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.     

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.     

DART+: Direction-aware bichromatic reverse k nearest neighbor query processing in spatial databases

This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B⁺-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBRkNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART.     

Consensus models: Computational complexity aspects in modern approaches to the list coloring problem

In the paper we study new approaches to the problem of list coloring of graphs. In the problem we are given a simple graph G=(V,E) and, for every v∈V, a nonempty set of integers S(v); we ask if there is a coloring c of G such that c(v)∈S(v) for every v∈V. Modern approaches, connected with applications, change the question—we now ask if S can be changed, using only some elementary transformations, to ensure that there is such a coloring and, if the answer is yes, what is the minimal number of changes. In the paper for studying the adding, the trading and the exchange models of list coloring, we use the following transformations:

•

adding of colors (the adding model): select two vertices u, v and a color c∈S(u); add c to S(v), i.e. set S(v):=S(v)∪{c};

•

trading of colors (the trading model): select two vertices u, v and a color c∈S(u); move c from S(u) to S(v), i.e. set S(u):=S(u)?{c} and S(v):=S(v)∪{c};

•

exchange of colors (the exchange model): select two vertices u, v and two colors c∈S(u), d∈S(v); exchange c with d, i.e. set S(u):=(S(u)?{c})∪{d} and S(v):=(S(v)?{d})∪{c}.

Our study focuses on computational complexity of the above models and their edge versions. We consider these problems on complete graphs, graphs with bounded cyclicity and partial k-trees, receiving in all cases polynomial algorithms or proofs of NP-hardness.     

On weakly cut-stable maps

A mapping f:P→Q between posets P and Q is called weakly cut-stable if f can be naturally extended to a weakly complete lattice homomorphism (i.e., preserving non-empty meets and joins) f^∗:N(P)→N(Q) between the corresponding Dedekind-MacNeille completions. These mappings are studied and described by the 1st-order language.     

Voxel-based surface area estimation: from theory to practice

Consider a complex, highly convoluted three-dimensional object that has been digitized and is available as a set of voxels. How can one estimate the (original, continuous) area of a region of interest on the surface of the object? The problem appears in the analysis of segmented MRI brain data and in other three-dimensional imaging applications. Several difficulties arise. First, due to the complexity of the surface and its foldings, the region of interest and its intended boundary can be concealed and are therefore difficult to delineate. Second, the correct surface topology on intricate voxel sets may not be obvious. Third, the surface area of a digital voxel world is generally very different than the area of the underlying continuous surface. These problems can be partly circumvented by transforming the voxel data to a polyhedral surface representation. Our challenge is to accomplish the task while maintaining the original voxel representation. Estimators for the continuous surface area of digital objects have been available for some time. However, the known methods are limited to fairly smooth and “well-behaved” surfaces. This research bridges the gap between the available surface area estimation theory, that applies to idealized settings, and the reality of MRI brain data. Surface connectivity ambiguities are alleviated by considering the object/background boundary voxel faces rather than the border voxels themselves. The region of interest on the surface is delimited by growing geodesic paths between user-provided anchor points. Surface estimation is extended to admit surfaces with higher curvature than previously considered. Performance evaluation results are provided, and operation on MRI brain data is demonstrated.     

Global Strong Defensive Alliances of Sierpiński-Like Graphs

A strong alliance in a graph G=(V,E) is a set of vertices S?V satisfying the condition that, for each v∈S, the number of its neighbors, including itself, in S is greater than the number of those neighbors not in S. A strong alliance S is global if S forms a dominating set of G. In this paper, we shall propose a way for finding a minimum global strong alliance for each of those Sierpiński-like graphs. Furthermore, we also derive the exact values of those global strong alliance numbers.     

An incremental space to visualize dynamic data sets

In Information Visualization, adding and removing data elements can strongly impact the underlying visual space. We have developed an inherently incremental technique (incBoard) that maintains a coherent disposition of elements from a dynamic multidimensional data set on a 2D grid as the set changes. Here, we introduce a novel layout that uses pairwise similarity from grid neighbors, as defined in incBoard, to reposition elements on the visual space, free from constraints imposed by the grid. The board continues to be updated and can be displayed alongside the new space. As similar items are placed together, while dissimilar neighbors are moved apart, it supports users in the identification of clusters and subsets of related elements. Densely populated areas identified in the incSpace can be efficiently explored with the corresponding incBoard visualization, which is not susceptible to occlusion. The solution remains inherently incremental and maintains a coherent disposition of elements, even for fully renewed sets. The algorithm considers relative positions for the initial placement of elements, and raw dissimilarity to fine tune the visualization. It has low computational cost, with complexity depending only on the size of the currently viewed subset, V. Thus, a data set of size N can be sequentially displayed in O(N) time, reaching O(N ²) only if the complete set is simultaneously displayed.