𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimally Distant Sets of Lattice Points

✍ Scribed by Daniel J. Kleitman; Leornard J. Schulman

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
393 KB
Volume
14
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of finding two sets of given cardinalities in certain grid graphs, so as to minimize the cross-distance between them. (This is the maximum Manhattan distance between points, one of the first set and another of the second set.) The question is answered completely for grids that are a product of chains of even edge length, and also for the (n)-cube, by way of the Clements-LindstrΓΆm approach.

πŸ“œ SIMILAR VOLUMES

Full Minimal Steiner Trees on Lattice Se
Full Minimal Steiner Trees on Lattice Sets
✍ M. Brazil; J.H. Rubinstein; D.A. Thomas; J.F. Weng; N.C. Wormald πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 497 KB

Given a finite set of points P in the Euclidean plane, the Steiner problem asks us to constuct a shortest possible network interconnecting P. Such a network is known as a minimal Steiner tree. The Steiner problem is an intrinsically difficult one, having been shown to be NP-hard [7]; however, it oft

Counting Lattice Points of Rational Poly
Counting Lattice Points of Rational Polyhedra
✍ Beifang Chen; Vladimir Turaev πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 153 KB

P : (n) x n: , where A is the set of all vertices of P and each P : (n) is a certain periodic function of n. The Ehrhart reciprocity law follows automatically from the above formula. We also present a formula for the coefficients of Ehrhart polynomials in terms of elementary symmetric functions. 200