Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?

Details Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town? Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?

2010-09-28

arxiv.org/abs/1009.5628v1

Computer Science

Computational Geometry

26 pages, 6 figures, to appear in Computational Geometry: Theory and Applications

Scientific paper

An n-town, for a natural number n, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings along the axis-parallel street grid, then an n-town has optimal shape if the sum of all pairwise Manhattan distances is minimized. This problem has been studied for cities, i.e., the limiting case of very large n. For cities, it is known that the optimal shape can be described by a differential equation, for which no closed-form is known. We show that optimal n-towns can be computed in O(n^7.5) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.

Affiliated with

Also associated with

No associations

Rating

Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integer Point Sets Minimizing Average Pairwise L1-Distance: What is the Optimal Shape of a Town? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-694729