✦ LIBER ✦

Embedding Pyramids into 3D Meshes

✍ Scribed by Cindy K.Y. Ng; Lawrence K.L. Pun; Dixon M.C. Ip; Mounir Hamdi; Ishfaq Ahmad

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 402 KB
Volume: 36
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.1996.0097

No coin nor oath required. For personal study only.

✦ Synopsis

The pyramid architecture is a powerful topology in the area of computer vision. On the other hand, the 3D mesh architecture possesses rich topological features which make it suitable for building scalable parallel processor systems. The usefulness of these two architectures has led us to consider the problem of embedding pyramids into 3D meshes, for which we present two solutions. The first solution, termed natural embedding, maps a pyramid into a 3D mesh such that each level of the pyramid is mapped to a single level of the 3D mesh. The second solution, termed multiple embedding, allows simultaneous embedding of multiple pyramids into a single 3D mesh. The quality of both solutions is evaluated using dilation and expansion measures. Using the multiple embedding, we are able to obtain an average dilation of 1.26 and a near-optimal expansion of 1.12.

📜 SIMILAR VOLUMES

Embedding multi-dimensional meshes into

Embedding multi-dimensional meshes into twisted cubes

✍ Qiang Dong; Xiaofan Yang; Dajin Wang 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 386 KB

The twisted cube is an important variant of the most popular hypercube network for parallel processing. In this paper, we consider the problem of embedding multi-dimensional meshes into twisted cubes in a systematic way. We present a recursive method for embedding a family of disjoint multi-dimensio

Optimal Embedding of Multiple Directed H

Optimal Embedding of Multiple Directed Hamiltonian Rings into d-dimensional Meshes

✍ Jae-Ha Lee; Chan-Su Shin; Kyung-Yong Chwa 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 167 KB

In this paper, we consider the embedding of multiple directed Hamiltonian rings into d-dimensional meshes M d . Assuming two adjacent nodes in M d are connected by two directed links with opposite directions, we aim to embed as many directed Hamiltonian rings as possible in a way that they are linkd

On embedding rectangular meshes into rec

On embedding rectangular meshes into rectangular meshes of smaller aspect ratio

✍ Shou-Hsuan S. Huang; Hongfei Liu; Rakesh M. Verma 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 598 KB

Let G = h x w be a rectangular grid and H = s x s be the optimal square grid for G, i.e., the least square grid which is no less than G in size. Let G' be the grid h' x W' such that s < W' < w and h' is the smallest integer such that hw 6 h'w'. In this paper, a (one-to-one) embedding scheme is pres

Embeddings of Star Graphs into Optical M

Embeddings of Star Graphs into Optical Meshes without Bends

✍ Stefan Thomas Obenaus; Ted H. Szymanski 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 377 KB

We show an embedding of the star graph into a rectangular optical multichannel mesh of d dimensions such that the embedding has no bends; that is, neighbors in the star graph always differ in exactly one coordinate in the mesh, to facilitate one-hop optical communication. To embed an n-star, the mes

Embedding Hypercubes and Related Network

Embedding Hypercubes and Related Networks into Mesh-Connected Processor Arrays

✍ F. Annexstein 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 736 KB

In this paper we study the problem of how computations programmed for hypercubes, and their bounded-degree relatives, the shuffle-exchange and cube-connected-cycles, can be efficiently emulated by mesh-connected arrays of processing elements. The emulations we present are implemented via graph embed

Optimal embedding of 2-D torus into ring

✍ Eva Ma; Bhagirath Narahari; Lixin Tao 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 443 KB