The k-Centrum Straight-line Location Problem | Journal of Mathematical Modelling and Algorithms in Operations Research Skip to main content
Springer Nature Link
Log in

The k-Centrum Straight-line Location Problem

  • Published:
Journal of Mathematical Modelling and Algorithms

Abstract

A line is sought in the plane which minimizes the sum of the k largest (Euclidean) weighted distances from n given points. This problem generalizes the known straight-line center and median problems and, as far as the authors are aware, has not been tackled up to now. By way of geometric duality it is shown that such a line may always be found which either passes through two of the given points or lying at equal weighted distance from three of these. This allows construction of an algorithm to find all t-centrum lines for 1 ≤ t ≤ k in O((k + logn)n 3). Finally it is shown that both, the characterization of an optimal line and the algorithm, can be extended to any smooth norm.

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

Access this article

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

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Agarwal, P.K., Aronov, B., Sharir, M.: Computing envelopes in four dimensions with applications. SIAM J. Comput. 26, 1714–1732 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  2. Chan, T.: Output-sensitive results on convex hulls, extreme points, and related problems. In: Proceedings of the 11th Annual Symposium on Computational Geometry, pp. 10–19 (1995)

  3. Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing kth-order Voronoi diagrams. Trans. Comput. C-36, 1349–1354 (1987)

    Article  MathSciNet  Google Scholar 

  4. De Berg, M., Van Krevel, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, New York (2000)

    MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  6. Edelsbrunner, H.: Finding traversals for sets of simple geometric figures. Theor. Comp. Sci. 35, 55–69 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  7. Houle, M.E., Imai, H., Imai, K., Robert, J.-M., Yamamoto, P.: Orthogonal weighted linear L 1 and L  ∞  approximations and applications. Discrete Appl. Math. 43, 217–232 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  8. Korneenko, N.M., Martini, H.: Hyperplane approximation and related topics. In: Pasch, J. (ed.) New Trends in Discrete and Computational Geometry, pp. 135–161. Springer, New York (1993)

    Google Scholar 

  9. Lee, D.T., Ching, Y.T.: The power of geometric duality revisited. Inf. Process. Lett. 21, 117–122 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  10. Lozano, A.J., Mesa, J.A., Plastria, F.: Improved results for the k-centrum straight-line location problem. In: Proceedings of the 20th European Workshop on Computational Geometry, pp. 217–219 (2004)

  11. MacKinnon, R., Barber, G.M.: A new approach to network generation and map representation: the linear case of the location-allocation problem. Geogr. Anal. 4, 156–168 (1972)

    Google Scholar 

  12. Martos, B.: Nonlinear Programming: Theory and Methods. North-Holland, Amsterdam (1975)

    MATH  Google Scholar 

  13. Morris, J.G., Norback, J.P.: Linear facility location-solving extensions on the basic problems. Eur. J. Oper. Res. 12, 90–94 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  14. Nandy, S.C., Das, S., Goswami, P.P.: An efficient k nearest neighbors searching algorithm for a query line. Theor. Comp. Sci. 299, 273–288 (2003)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  16. Romeijn, H.E., Ahuja, R.K., Dempsey, J.F., Kumar, A.: A new linear programming approach to radiation therapy treatment planning problems. Oper. Res. 54, 201–216 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  17. Schöbel, A.: Locating Lines and Hyperplanes-Theory and Algorithms. Kluwer Academic, Dordrecht (1999)

    MATH  Google Scholar 

  18. Sharir, M., Smorodinsky, S., Tardos, G.: An improved bound for k-sets in three dimensions. Discrete Comput. Geom. 26, 195–204 (2001)

    MATH  MathSciNet  Google Scholar 

  19. Tamir, A.: The k-centrum multi-facility location problem. Discrete Appl. Math. 109, 293–307 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  20. Wesolowsky, G.O.: Location of the median line for weighted points. Environ. Plann. A 7, 163–170 (1975)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemáticas, Facultad de Ciencias Experimentales, University of Huelva, Bulevar de las Artes y las Ciencias s/n, 21071, Huelva, Spain

    Antonio J. Lozano

  2. Departamento de Matemática Aplicada II, University of Seville, Camino de los Descubrimientos s/n, 41092, Seville, Spain

    Juan A. Mesa

  3. MOSI—Department of Mathematics, Operational Research, Statistics and Information Systems for Management, Vrije Universiteit Brussel, Pleinlaan 2, 1050, Brussel, Belgium

    Frank Plastria

Authors
  1. Antonio J. Lozano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juan A. Mesa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Frank Plastria
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Frank Plastria.

Additional information

A. J. Lozano and J. A. Mesa were partially supported by Project MCyT BFM2003-04062/MATE.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lozano, A.J., Mesa, J.A. & Plastria, F. The k-Centrum Straight-line Location Problem. J Math Model Algor 9, 1–17 (2010). https://doi.org/10.1007/s10852-009-9119-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10852-009-9119-z

Keywords

Search

Navigation