Narrow Results

A graph G* is k-edge fault-tolerant with respect to a graph G, denoted by k-EFT(G), if every graph obtained by removing any k edges from G* contains G. A k-EFT(G) graph is optimal if it contains the minimum number of edges among all k-EFT(G) graphs. Recently, Harary and Hayes have presented a design which is 1-EFT with respect to meshes and conjectured that their design is optimal. We prove their conjecture is false by giving another design which is 1-EFT with respect to meshes.

The main contribution of this work is to show that a number of digital geometry problems can be solved elegantly on meshes with multiple broadcasting by using a time-optimal solution to the leftmost one problem as a basic subroutine. Consider a binary image pretiled onto a mesh with multiple broadcasting of size one pixel per processor. Our first contribution is to prove an Ω(n^1/6) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically, the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n^1/6) time algorithms for these problems. As previously mentioned, an interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.

We propose two mechanisms that can be used to generate complex geometry: generalized subdivision and mesh-based parametrized L-Systems. Instead of using standard subdivision, which uses the same subdivision rule at each level of the subdivision process, in order to converge to a limit surface, we employ a generalized approach, that allows different subdivision rules at each level. By limiting the variations at each level, it is possible to ensure convergence. Mesh-based parametrized L-Systems represent an extension to L-systems which associates symbols to the faces in a mesh. Thereby complex geometry can be introduced into an existing mesh by using procedural substitution rules. Combining both these mechanisms, a wide variety of complex models can be easily generated from very compact representations.

Elsewhere we have introduced a construction to produce biorthogonal multiresolutions from given subdivisions. This construction was formulated in matrix terms, which is appropriate for curves and tensor-product surfaces. For mesh surfaces of non-tensor connectivity, however, matrix notation is inconvenient. This work presents the construction for regular meshes using diagrams (stencils, masks) and interactions between diagrams to replace matrices and matrix multiplication. Regular triangular meshes with butterfly subdivision and a variant of Loop subdivision due to Litke, et al. are used as examples.

Index-shuffle graphs are a family of bounded-degree hypercube-like interconnection networks for parallel computers, introduced by [Baumslag and Obrenić (1997): Index-Shuffle Graphs, …], as an efficient substitute for two standard families of hypercube derivatives: butterflies and shuffle-exchange graphs. In the theoretical framework of graph embedding and network emulations, this paper shows that the index-shuffle graph efficiently approximates the direct-product structure of the hypercube, and thereby has a unique potential to approximate efficiently all of its derivatives.

One of the consequences of our results is that any member of the following group of standard bounded-degree hypercube derivatives: butterflies, shuffles, tori, meshes of trees, is emulated by the index-shuffle graph with a slowdown in the order of the logarithm of the slowdown of the most efficient emulation achieved by any other member of this group.

Emulation algorithms are presented where the emulation host is the n-dimensional index-shuffle graph Ψ_n, having N=2ⁿ nodes. The emulated graph G is a direct product of the form: G=F₀×F₁×⋯×F_k-1 where k is a power of 2, and each factor F_i is an instance of any of the following three graph families: cycle, complete binary tree, X-tree. Let the size of each factor be |F_i|≤2^n_f, where k·n_f≤n. The index-shuffle graph Ψ_n, emulates any factor F_i in the product G with slowdown: O(log k) + O(log n_f), which is O(log n) = O(loglog N). Any collection of 2^ℓ copies of the product G, such that: ℓ+k·n_f≤n is emulated by the index-shuffle graph Ψ_n simultaneously, without any additional slowdown. Relaxing the assumption that k is a power of 2 introduces an additional factor of O(lg*N) into the slowdown.

Classical approaches of feature line detection rely on curvature derivatives. They generally suffer from a common problem: the connectivity is hard to obtain and it is impossible to generate intersections between feature lines. This article presents a method to extract feature lines on 3D meshes. In order to sort out the recurrent issues of traditional approaches, we propose a novel algorithm based on two ideas. First, all the mesh vertices are marked according to the curvature values: a binary map with candidate regions is then constructed. The second idea is to isolate each candidate region and transform it into a line. To achieve this, we parameterize the region into its 2D regular representation. We then perform a skeletonization to obtain lines with high connectivity. By applying the inverse parameterization, the feature lines are mapped back onto the 3D mesh. In the end, we extract perceptual salient parts and above all connected feature lines. In order to evaluate and validate our algorithm, we compare our method to classical ones and apply our technique to a geological context.

The main contribution of this work is to show that a number of digital geometry problems can be solved elegantly on meshes with multiple broadcasting by using a time-optimal solution to the leftmost one problem as a basic subroutine. Consider a binary image pretiled onto a mesh with multiple broadcasting of size one pixel per processor. Our first contribution is to prove an Ω(n^1/6) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically, the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n^1/6) time algorithms for these problems. As previously mentioned, an interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.