Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town?
Special issue of selected papers from the 21st Annual Canadian Conference on Computational Geometry
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier B.V.
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62244 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1811086711697965056 |
|---|---|
| author | Demaine, Erik D. Fekete, Sandor P. Rote, Günter Schweer, Nils Schymura, Daria Zelke, Mariano |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Fekete, Sandor P. Rote, Günter Schweer, Nils Schymura, Daria Zelke, Mariano |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | Special issue of selected papers from the 21st Annual Canadian Conference on Computational Geometry |
| first_indexed | 2024-09-23T13:31:55Z |
| format | Article |
| id | mit-1721.1/62244 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:31:55Z |
| publishDate | 2011 |
| publisher | Elsevier B.V. |
| record_format | dspace |
| spelling | mit-1721.1/622442022-09-28T14:37:28Z Integer point sets minimizing average pairwise L[subscript 1] 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? Demaine, Erik D. Fekete, Sandor P. Rote, Günter Schweer, Nils Schymura, Daria Zelke, Mariano Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Demaine, Erik D. Special issue of selected papers from the 21st Annual Canadian Conference on Computational Geometry An n-town, n[is an element of]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(n[superscript 7.5]) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80. 2011-04-19T20:58:44Z 2011-04-19T20:58:44Z 2010-09 2009-11 Article http://purl.org/eprint/type/ConferencePaper 0925-7721 http://hdl.handle.net/1721.1/62244 Demaine, Erik D. et al. “Integer Point Sets Minimizing Average Pairwise L1 Distance: What Is the Optimal Shape of a Town?” Computational Geometry 44.2 (2011) : 82-94. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1016/j.comgeo.2010.09.004 Computational Geometry: Theory and Applications Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Elsevier B.V. MIT web domain |
| spellingShingle | Demaine, Erik D. Fekete, Sandor P. Rote, Günter Schweer, Nils Schymura, Daria Zelke, Mariano Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town? |
| title | Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town? |
| title_full | Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town? |
| title_fullStr | Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town? |
| title_full_unstemmed | Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town? |
| title_short | Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town? |
| title_sort | integer point sets minimizing average pairwise l subscript 1 distance what is the optimal shape of a town |
| url | http://hdl.handle.net/1721.1/62244 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd integerpointsetsminimizingaveragepairwiselsubscript1distancewhatistheoptimalshapeofatown AT feketesandorp integerpointsetsminimizingaveragepairwiselsubscript1distancewhatistheoptimalshapeofatown AT rotegunter integerpointsetsminimizingaveragepairwiselsubscript1distancewhatistheoptimalshapeofatown AT schweernils integerpointsetsminimizingaveragepairwiselsubscript1distancewhatistheoptimalshapeofatown AT schymuradaria integerpointsetsminimizingaveragepairwiselsubscript1distancewhatistheoptimalshapeofatown AT zelkemariano integerpointsetsminimizingaveragepairwiselsubscript1distancewhatistheoptimalshapeofatown AT demaineerikd integerpointsetsminimizingaveragepairwisel1distancewhatistheoptimalshapeofatown AT feketesandorp integerpointsetsminimizingaveragepairwisel1distancewhatistheoptimalshapeofatown AT rotegunter integerpointsetsminimizingaveragepairwisel1distancewhatistheoptimalshapeofatown AT schweernils integerpointsetsminimizingaveragepairwisel1distancewhatistheoptimalshapeofatown AT schymuradaria integerpointsetsminimizingaveragepairwisel1distancewhatistheoptimalshapeofatown AT zelkemariano integerpointsetsminimizingaveragepairwisel1distancewhatistheoptimalshapeofatown |