Skip to main content
SpringerLink
Log in

Locating an axis-parallel rectangle on a Manhattan plane

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

In this paper we consider the problem of locating an axis-parallel rectangle in the plane such that the sum of distances between the rectangle and a finite point set is minimized, where the distance is measured by the Manhattan norm ℓ 1. In this way we solve an extension of the Weber problem to extensive facility location. As a model, our problem is appropriate for position sensing of rectangular objects.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Bauer FL, Stoer J, Witzgall C (1961) Absolute and monotonic norms. Numer Math 3:257–264

    Article  Google Scholar 

  • Bern M, Goldberg D (2002) Paper position sensing. In: SCG’02: proceedings of the eighteenth annual symposium on computational geometry, pp 74–81

    Chapter  Google Scholar 

  • Brimberg J, Juel H, Körner M, Schöbel A (2011) Locating a general minisum circle on the plane. 4OR. doi:10.1007/s10288-011-0169-5

    Google Scholar 

  • Brimberg J, Juel H, Schöbel A (2002) Linear facility location in three dimensions: Models and solution methods. Oper Res 50:1050–1057

    Article  Google Scholar 

  • Brimberg J, Juel H, Schöbel A (2003) Properties of 3-dimensional line location models. Ann Oper Res 122:71–85

    Article  Google Scholar 

  • Brimberg J, Juel H, Schöbel A (2007) Locating a circle on a sphere. Oper Res 55:782–791

    Article  Google Scholar 

  • Brimberg J, Juel H, Schöbel A (2009) Locating a minisum circle in the plane. Discrete Appl Math 157:901–912

    Article  Google Scholar 

  • Brimberg J, Wesolowsky G (2000) Note: facility location with closest rectangular distances. Nav Res Logist 47:77–84

    Article  Google Scholar 

  • Brimberg J, Wesolowsky G (2002) Minisum location with closest Euclidean distances. Ann Oper Res 111:151–165

    Article  Google Scholar 

  • Díaz-Báñez JM, Mesa JA, Schöbel A (2004) Continuous location of dimensional structures. Eur J Oper Res 152(1):22–44

    Article  Google Scholar 

  • Drezner Z, Klamroth K, Schöbel A, Wesolowsky G (2002) The Weber problem. In: Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin, pp 1–36

    Chapter  Google Scholar 

  • Drezner Z, Steiner G, Wesolowsky G (2002) On the circle closest to a set of points. Comput Oper Res 29:637–650

    Article  Google Scholar 

  • Gluchshenko O, Hamacher H, Tamir A (2009) An optimal O(nlogn) algorithm for finding an enclosing planar annulus of minimum width. Oper Res Lett 37:168–170

    Article  Google Scholar 

  • Grimson W (1991) Object recognition by computer. The MIT Press, Cambridge

    Google Scholar 

  • Hassin R, Tamir A (1991) Improved complexity bounds for location problems on the real line. Oper Res Lett 10:395–402

    Article  Google Scholar 

  • Korneenko N, Martini H (1990) Approximating finite weighted point sets by hyperplanes. In: SWAT’90: proceedings of the 2nd Scandinavian workshop on algorithm theory, pp 276–286

    Google Scholar 

  • Korneenko N, Martini H (1993) Hyperplane approximation and related topics. In: Pach J (ed) New trends in discrete and computational geometry. Springer, Berlin, pp 135–162

    Chapter  Google Scholar 

  • Körner M (2011) Minisum hyperspheres. Springer, Berlin

    Book  Google Scholar 

  • Körner M, Brimberg J, Juel H, Schöbel A (2009) General minisum circle location. In: Proceedings of the 21th Canadian conference on computational geometry, pp 111–114

    Google Scholar 

  • Körner M, Brimberg J, Juel H, Schöbel A (2011) Geometric fit of a point set by generalized circles. J Glob Optim 51:115–132

    Article  Google Scholar 

  • Love R, Morris J, Wesolowsky G (1988) Facilities location—models & methods. North-Holland, Amsterdam

    Google Scholar 

  • Martini H, Schöbel A (1998) Median hyperplanes in normed spaces—a survey. Discrete Appl Math 89:181–193

    Article  Google Scholar 

  • Martini H, Schöbel A (1999) Two characterizations of smooth norms. Geom Dedic 77:173–183

    Article  Google Scholar 

  • Martini H, Schöbel A (2001) Median and center hyperplanes in Minkowski spaces—a unified approach. Discrete Math 241:407–426

    Article  Google Scholar 

  • Plastria F, Carrizosa E (2001) Gauge distances and median hyperplanes. J Optim Theory Appl 110:173–182

    Article  Google Scholar 

  • Schöbel A (1999) Locating lines and hyperplanes: theory and algorithms. Kluwer Academic, Dordrecht

    Book  Google Scholar 

  • Schöbel A (2003) Anchored hyperplane location problems. Discrete Comput Geom 29(2):229–238

    Article  Google Scholar 

  • Schöbel A, Scholz D (2010) The big cube small cube solution method for multidimensional facility location problems. Comput Oper Res 37:115–122

    Article  Google Scholar 

  • Wallack A, Canny J, Manocha D (1993) Object localization using crossbeam sensing. In: IEEE international conference on robotics and automation

    Google Scholar 

  • Weber A (1909) Über den Standort der Industrien. Tübingen (in German)

  • Wesolowsky G (1975) Location of the median line for weighted points. Environ Plan A 7:163–170

    Article  Google Scholar 

Download references

Acknowledgements

We wish to thank two anonymous referees for their helpful comments. An improved complexity bound on the algorithms given is due to a suggestion by Professor Arie Tamir, and we are also very thankful for that.

Author information

Authors and Affiliations

  1. Royal Military College, Canada and Groupe d’Études et de Recherche en Analyse des Décisions, Kingston, Canada

    Jack Brimberg

  2. Technical University of Denmark, Lyngby, Denmark

    Henrik Juel

  3. Georg-August-Universität Göttingen, Göttingen, Germany

    Mark-Christoph Körner & Anita Schöbel

Authors
  1. Jack Brimberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Henrik Juel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mark-Christoph Körner
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Anita Schöbel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Henrik Juel.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brimberg, J., Juel, H., Körner, MC. et al. Locating an axis-parallel rectangle on a Manhattan plane. TOP 22, 185–207 (2014). https://doi.org/10.1007/s11750-012-0248-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-012-0248-6

Keywords

Mathematics Subject Classification (2000)

Search

Navigation