Accession Number : ADA195287

Title :   Embedding Rectangular Grids into Square Grids with Dilation Two.

Descriptive Note : Technical rept.,

Corporate Author : PITTSBURGH UNIV PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Melham, Rami ; Hwang, Ghil-Young

PDF Url : ADA195287

Report Date : Jan 1988

Pagination or Media Count : 21

Abstract : In this paper, a new technique, the multiple ripple propagation technique, is presented for mapping an h x w grid into an w x h grid such that the dilation cost is 2. That is, such that any two neighboring nodes in the first grid are mapped into two nodes in the second grid that are at most distance 2 apart. This technique is then used as a basic tool for mapping any rectangular source grid into a square target grid with the dilation two property preserved. The ratio of the number of nodes in the source grid to the number of nodes in the target grid, called the expansion cost, is shown to be always less than 1.2. This is a noticeable improvement over the previously suggested techniques in which the expansion cost could be bounded by 1.2 only if the dilation cost is allowed to be as high as 18.

Descriptors :   *EMBEDDING, *GRIDS, COSTS, NODES, PROPAGATION, RATIOS, RIPPLES, TOOLS, MAPPING, COMPUTER GRAPHICS

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE