A competitive strategy for distance-aware online shape allocation. (English) Zbl 1360.68875
Summary: We consider the following online allocation problem: Given a unit square \(S\), and a sequence of numbers \(n_i \in [0, 1]\) with \(\sum_{j = 0}^i n_j \leqslant 1\); at each step \(i\), select a region \(C_i\) of previously unassigned area \(n_i\) in \(S\). The objective is to make these regions compact in a distance-aware sense: minimize the maximum (normalized) average Manhattan distance between points from the same set \(C_i\). Related location problems have received a considerable amount of attention; in particular, the problem of determining the “optimal shape of a city”, i.e., allocating a single \(n_i\) has been studied. We present an online strategy, based on an analysis of space-filling curves; for continuous shapes, we prove a factor of 1.8092, and 1.7848 for discrete point sets.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68W27 | Online algorithms; streaming algorithms |
Keywords:
clustering; average distance; online problems; optimal shape of a city; space-filling curves; competitive analysisReferences:
| [1] | Bender, C. M.; Bender, M. A.; Demaine, E. D.; Fekete, S. P., What is the optimal shape of a city?, J. Phys. A, 37, 1, 147-159 (2004) · Zbl 1046.90538 |
| [2] | Bender, M. A.; Bunde, D. P.; Demaine, E. D.; Fekete, S. P.; Leung, V. J.; Meijer, H.; Phillips, C. A., Communication-aware processor allocation for supercomputers: finding point sets of small average distance, Algorithmica, 50, 2, 279-298 (2008) · Zbl 1141.68017 |
| [3] | Dai, H.-K.; Su, H.-C., On the locality properties of space-filling curves, (14th International Symposium on Algorithms and Computation (ISAAC) (2003)), 385-394 · Zbl 1205.68476 |
| [4] | de Berg, M.; Speckmann, B.; van der Weele, V., Treemaps with bounded aspect ratio, (22nd International Symposium on Algorithms and Computation (ISAAC) (2011)), 260-270 · Zbl 1350.68270 |
| [5] | Demaine, E. D.; Fekete, S. P.; Rote, G.; Schweer, N.; Schymura, D.; Zelke, M., Integer point sets minimizing average pairwise L1 distance: what is the optimal shape of a town?, Comput. Geom., 40, 82-94 (2011) · Zbl 1208.65085 |
| [6] | Fekete, S. P.; Schweer, N.; Reinhardt, J., A competitive strategy for distance-aware online shape allocation, (7th International Workshop on Algorithms and Computation (WALCOM) (2013)), 41-52 · Zbl 1379.68324 |
| [7] | Gotsman, C.; Lindenbaum, M., On the metric properties of discrete space-filling curves, IEEE Trans. Image Process., 5, 5, 794-797 (1996) |
| [8] | Karp, R. M.; McKellar, A. C.; Wong, C. K., Near-optimal solutions to a 2-dimensional placement problem, SIAM J. Comput., 4, 3, 271-286 (1975) · Zbl 0355.68044 |
| [9] | Krumke, S.; Marathe, M.; Noltemeier, H.; Radhakrishnan, V.; Ravi, S.; Rosenkrantz, D., Compact location problems, Theoret. Comput. Sci., 181, 2, 379-404 (1997) · Zbl 0902.90114 |
| [10] | Leung, J. Y.-T.; Tam, T. W.; Wing, C. S.; Young, G. H.; Chin, F. Y., Packing squares into a square, J. Parallel Distrib. Comput., 10, 3, 271-275 (1990) |
| [11] | Leung, V. J.; Arkin, E. M.; Bender, M. A.; Bunde, D. P.; Johnston, J.; Lal, A.; Mitchell, J. S.B.; Phillips, C. A.; Seiden, S. S., Processor allocation on Cplant: achieving general processor locality using one-dimensional allocation strategies, (Proc. IEEE CLUSTER’02 (2002)), 296-304 |
| [12] | Niedermeier, R.; Reinhardt, K.; Sanders, P., Towards optimal locality in mesh-indexings, Discrete Appl. Math., 117, 1-3, 211-237 (2002) · Zbl 1004.68181 |
| [13] | Sagan, H., Space-Filling Curves (1994), Springer: Springer New York · Zbl 0806.01019 |
| [14] | Schweer, N., Algorithms for packing problems (2010), PhD thesis, Braunschweig · Zbl 1304.90002 |
| [15] | Siromoney, R.; Subramanian, K., Space-filling curves and infinite graphs, (Graph Grammars and Their Application to Computer Science. Graph Grammars and Their Application to Computer Science, Lecture Notes in Comput. Sci., vol. 153 (1983), Springer: Springer Berlin), 380-391 · Zbl 0519.68068 |
| [16] | Wattenberg, M., A note on space-filling visualizations and space-filling curves, (Proceedings of the IEEE Symposium on Information Visualization (INFOVIS) (2005)), 181-186 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
