Skip to main content
SpringerLink
Log in

Optimal circle covering problems and their applications

  • Original Paper
  • Published:
Central European Journal of Operations Research Aims and scope Submit manuscript

Abstract

We study a special type of circle covering problem, the complete cover of polygons by not necessarily congruent circles with prescribed centres. We introduce a branch-and-bound algorithm which is able to check whether an actual set of circles covers a given polygon. Furthermore, we present a method capable of finding the optimal cover with arbitrary precision. These techniques are based on interval arithmetic, therefore our results are numerically reliable. To demonstrate the performance of the developed optimization method, we determine the optimal cover of the unit square and an irregular polygon.

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

Similar content being viewed by others

References

  • Alefeld G, Herzberger J (1983) Introduction to interval computations. Academic Press Inc., New York

    MATH  Google Scholar 

  • Alefeld G, Mayer G (2000) Interval analysis: theory and applications. J Comput Appl Math 121:421–464

    Article  MATH  MathSciNet  ADS  Google Scholar 

  • Antal E, Csendes T, Virágh J (2013) Nonlinear transformations for the simplification of unconstrained nonlinear optimization problems. Cent Eur J Oper Res 21:665–684

    Article  Google Scholar 

  • Bánhelyi B, Csendes T, Garay BM, Hatvani L (2008) A computer-assisted proof of \(\Sigma _{3}\)-chaos in the forced damped pendulum equation. SIAM J Appl Dyn Syst 7(3):843–867

    Article  MATH  MathSciNet  Google Scholar 

  • Cambini R, Sodini C (2008) A computational comparison of some branch and bound methods for indefinite quadratic programs. Cent Eur J Oper Res 16:139–152

    Article  MATH  MathSciNet  Google Scholar 

  • Casado LG, García I, Csendes T (2000) A new multisection technique in interval methods for global optimization. Computing 65:263–269

    Article  MATH  MathSciNet  Google Scholar 

  • Casado LG, García I, Tóth BG, Hendrix EMT (2011) On determining the cover of a simplex by spheres centered at its vertices. J Global Optim 50:645–655

    Article  MATH  MathSciNet  Google Scholar 

  • Csendes T (2001) New subinterval selection criteria for interval global optimization. J Global Optim 19:307–327

  • Csendes T, Garay BM, Bánhelyi B (2006) A verified optimization technique to locate chaotic regions of a Hénon system. J Global Optim 35:145–160

    Article  MATH  MathSciNet  Google Scholar 

  • C-XSC Language home page. http://www.xsc.de/

  • Das GK, Das S, Nandy SC, Shina BS (2006) Efficient algorithm for placing a given number of base station to cover a convex region. J Parallel Distrib Comput 66:1353–1358

    Article  MATH  Google Scholar 

  • Friedman E (2014) Circles covering squares web page. http://www2.stetson.edu/~efriedma/circovsqu/

  • Heppes A (2006) Covering a planar domain with sets of small diameter. Periodica Mathematica Hungarica 53:157–168

    Article  MATH  MathSciNet  Google Scholar 

  • Heppes A, Melissen H (1997) Covering a rectangle with equal circles. Periodica Mathematica Hungarica 34:65–81

    Article  MATH  MathSciNet  Google Scholar 

  • Huang WQ, Ye T (2011) Quasi-physical global optimization method for solving the equal circle packing problem. Sci China Inf Sci 54:1333–1339

    Article  MATH  MathSciNet  Google Scholar 

  • Kubach T, Bortfeldt A, Gehring H (2009) Parallel greedy algorithms for packing unequal circles into a strip or a rectangle. Cent Eur J Oper Res 17:461–477

    Article  MATH  MathSciNet  Google Scholar 

  • Nurmela KJ (2000) Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles. Exp Math 9:241–250

    Article  MATH  MathSciNet  Google Scholar 

  • Pál L, Csendes T (2009) Intlab implementation of an interval global optimization algorithm. Optim Methods Softw 24:749–759

    Article  MATH  MathSciNet  Google Scholar 

  • Palatinus E (2010) Optimal and reliable covering of planar objects with circles. In: Proceedings of the 2010 mini-conference on applied theoretical computer science

  • Ratschek H, Rokne J (1988) New computer methods for global optimization. Ellis Horwood, Chichester

    MATH  Google Scholar 

  • Shimrat M (1962) Algorithm 112, position of point relative to polygon. Commun ACM 5(8):434

    Article  Google Scholar 

  • Vinkó T, Ratz D (2004) A multidimensional branch-and-prune method for interval global optimization. Numer Algorithms 37:391–399

    Article  MATH  MathSciNet  ADS  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Informatics, University of Szeged, Szeged, Hungary

    Balázs Bánhelyi & Balázs L. Lévai

  2. Information Systems Group, Saarland University, Saarbrücken, Germany

    Endre Palatinus

Authors
  1. Balázs Bánhelyi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Endre Palatinus
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Balázs L. Lévai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Balázs Bánhelyi.

Additional information

E. Palatinus: work done while at the University of Szeged.

The publication is supported by the European Union and co-founded by the European Social Fund. Project title: “Telemedicine-focused research activities on the field of Mathematics, Informatics and Medical sciences”. Project No.: TÁMOP-4.2.2.A-11/1/KONV-2012-0073.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bánhelyi, B., Palatinus, E. & Lévai, B.L. Optimal circle covering problems and their applications. Cent Eur J Oper Res 23, 815–832 (2015). https://doi.org/10.1007/s10100-014-0362-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10100-014-0362-7

Keywords

Search

Navigation