A Competitive Strategy for Distance-Aware Online Shape Allocation | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Competitive Strategy for Distance-Aware Online Shape Allocation

  • Conference paper
WALCOM: Algorithms and Computation (WALCOM 2013)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7748))

Included in the following conference series:

  • 1021 Accesses

Abstract

We consider the following online allocation problem: Given a unit square S, and a sequence of numbers n i  ∈ {0,1} with \(\sum_{j=0}^i n_j\leq 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, both in a continuous and a discrete setting. 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Bender, C.M., Bender, M.A., Demaine, E.D., Fekete, S.P.: What is the optimal shape of a city? J. Physics A: Mathematical and General 37(1), 147–159 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  3. Dai, H.K., Su, H.C.: On the Locality Properties of Space-Filling Curves. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 385–394. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  4. de Berg, M., Speckmann, B., van der Weele, V.: Treemaps with bounded aspect ratio. CoRR, abs/1012.1749 (2010)

    Google Scholar 

  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? Comp. Geom. 40, 82–94 (2011)

    Article  MathSciNet  Google Scholar 

  6. Gotsman, C., Lindenbaum, M.: On the metric properties of discrete space-filling curves. IEEE Transactions on Image Processing 5(5), 794–797 (1996)

    Article  Google Scholar 

  7. Karp, R.M., McKellar, A.C., Wong, C.K.: Near-Optimal Solutions to a 2-Dimensional Placement Problem. SIAM J. Computing 4(3), 271–286 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  8. Krumke, S., Marathe, M., Noltemeier, H., Radhakrishnan, V., Ravi, S., Rosenkrantz, D.: Compact location problems. Theor. Comput. Sci. 181(2), 379–404 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  9. 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)

    Article  MathSciNet  Google Scholar 

  10. 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. In: Proc. IEEE CLUSTER 2002, pp. 296–304 (2002)

    Google Scholar 

  11. Niedermeier, R., Reinhardt, K., Sanders, P.: Towards optimal locality in mesh-indexings. Discrete Applied Mathematics 117(1-3), 211–237 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  12. Sagan, H.: Space-Filling Curves. Springer, New York (1994)

    Book  MATH  Google Scholar 

  13. Schweer, N.: Algorithms for Packing Problems. PhD thesis, Braunschweig (2010)

    Google Scholar 

  14. Siromoney, R., Subramanian, K.: Space-filling Curves and Infinite Graphs. In: Ehrig, H., Nagl, M., Rozenberg, G. (eds.) Graph Grammars 1982. LNCS, vol. 153, pp. 380–391. Springer, Heidelberg (1983)

    Chapter  Google Scholar 

  15. Wattenberg, M.: A note on space-filling visualizations and space-filling curves. In: Proceedings of the IEEE Symposium on Information Visualization, INFOVIS, pp. 181–186 (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, TU Braunschweig, Germany

    Sándor P. Fekete, Nils Schweer & Jan-Marc Reinhardt

Authors
  1. Sándor P. Fekete
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nils Schweer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jan-Marc Reinhardt
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Technology and Computer Science, Tata Institute of Fundamental Research, Homi Bhabha Road, 400005, Mumbai, India

    Subir Kumar Ghosh

  2. Graduate School of Information Sciences (GSIS), Tohoku University, Aobayama Campus, GSIS Building, 980-8578, Sendai, Japan

    Takeshi Tokuyama

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fekete, S.P., Schweer, N., Reinhardt, JM. (2013). A Competitive Strategy for Distance-Aware Online Shape Allocation. In: Ghosh, S.K., Tokuyama, T. (eds) WALCOM: Algorithms and Computation. WALCOM 2013. Lecture Notes in Computer Science, vol 7748. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36065-7_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-36065-7_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-36064-0

  • Online ISBN: 978-3-642-36065-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation