0
喜欢
0
书签
声明论文
Integer point sets minimizing average pairwise L   
摘  要:   An n-town, n∈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 solution is known. We show that optimal n-towns can be computed in O(n7.5) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.
发  表:   Computational Geometry: Theory and Applications  2011

共享有3个版本

Bibtex
创新指数 
阅读指数 
重现指数 
论文点评
还没有人点评哦

Feedback
Feedback
Feedback
我想反馈:
排行榜