Stereoscopic families of permutations, and their applications

摘要: A stereoscopic family of permutations maps an m-dimensional mesh into several 1-dimensional lines, in a way that jointly preserves distance information. Specifically, consider any two points and denote their on the by d. Then between images, line which these images are closest together is O(d/sup m/). We initiate systematic study families permutations. show construction involves use m+1 images. also under some additional restrictions (namely adjacent image lines originate at not too far away mesh), three necessary order to construct such for 2-dimensional mesh. present applications One application algorithm routing guarantees delivery each packet within number steps depends upon this packet's source destination, but independent size Our exceptionally simple, no queues, can be used dynamic settings packets continuously generated. Another extension nonexpansive hash functions Linial Sasson (STOC 96) from case one dimensional metrics arbitrary dimensions.