𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Embedding into the rectilinear grid

✍ Scribed by Bandelt, Hans-J�rgen; Chepoi, Victor

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
108 KB
Volume
32
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the embedding of metric spaces into the l 1 -grid ‫ޚ‬ 2 can be characterized in essentially the same fashion as in the case of the l 1 -plane ‫ޒ‬ 2 . In particular, a metric space can be embedded into ‫ޚ‬ 2 iff every subspace with at most 6 points is embeddable. Moreover, if such an embedding exists, it can be constructed in polynomial time (for finite spaces).

📜 SIMILAR VOLUMES

A grid embedding into the star graph for
A grid embedding into the star graph for image analysis solutions
✍ Nayla Nassif; Nader Bagherzadeh 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 596 KB

In this paper, we model the star interconnection network with a graph and present an innovative grid embedding into it. The embedding is specifically designed and optimized for image analysis solutions. Using the embedding, we outline the general approach for solving such problems on the star graph

Dilation-5 Embedding of 3-Dimensional Gr
Dilation-5 Embedding of 3-Dimensional Grids into Hypercubes
✍ M.Y. Chan; F. Chin; C.N. Chu; W.K. Mak 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 271 KB

We present an algorithm to map the nodes of a 3-dimensional grid to the nodes of its optimal hypercube on a one-to-one basis with dilation at most 5.

Embeddings of Hypercubes and Grids into
Embeddings of Hypercubes and Grids into de Bruijn Graphs
✍ M.C. Heydemann; J. Opatrny; D. Sotteau 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 644 KB

An embedding of a graph \(G\) into a graph \(H\) is an injective mapping \(f\) from the vertices of \(G\) into the vertices of \(H\) together with a mapping \(P_{f}\) of edges of \(G\) into paths in \(H\). The dilation of the embedding is the maximum taken over all the lengths of the paths \(P_{f}(x

Embedding ladders and caterpillars into
Embedding ladders and caterpillars into the hypercube
✍ Sergei Bezrukov; Burkhard Monien; Walter Unger; Gerd Wechsung 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 594 KB

We present an embedding of generalized ladders as subgraphs into the hypercube. Through an embedding of caterpillars into ladders, we obtain an embedding of caterpillars into the hypercube. In this way we get almost all known results concerning the embedding of caterpillars into the hypercube. In ad

Embedding the attribute information into
Embedding the attribute information into a dithered image
✍ Kiyoshi Tanaka; Yasuhiro Nakamura; Kineo Matsui Members 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 677 KB

## Abstract Attribute information is indispensable data in the collection and storage of a large amount of image information. If these data are stored together with the image, handling of the materials would become simpler and more reliable. This paper proposes a method to embed the attribute infor