Skip to main content
SpringerLink
Log in

Covering a compact polygonal set by identical circles

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

The paper considers the problem of covering compact polygonal set by identical circles of minimal radius. A mathematical model of the problem based on Voronoi polygons is constructed and its characteristics are investigated. On the ground of the characteristics a modification of the Zoutendijk feasible directions method is developed to search local minima. A special approach is suggested to choose starting points. Many computational examples are given.

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

Similar content being viewed by others

References

  1. Berge, Cl.: Topological Spaces. Oliver and Boyd, Edinburgh (1963)

    MATH  Google Scholar 

  2. Sloane, N.J.A.: with the collaboration of Hardin, R.H., Smith, W.D., et al.: Tables of spherical codes. http://www.research.att.com/~njas/packings/

  3. Melissen, H.: Packing and covering with circles. PhD thesis, Universiteit Utrecht, the Netherlands (1997)

  4. Zahn, C.T. Jr.: Black box maximization of circular coverage. J. Res. Nat. Bur. Stand. Sect. B 66, 181–216 (1962)

    MATH  MathSciNet  Google Scholar 

  5. Tarnai, T., Gaspar, Zs.: Covering a square by equal circles. Elem. Math. 50, 167–170 (1995)

    MATH  MathSciNet  Google Scholar 

  6. Rogers, C.A.: Packing and Covering. Cambridge University Press, Cambridge (1964)

    MATH  Google Scholar 

  7. Melissen, J.B.M., Schuur, P.C.: Improved coverings of a square with six and eight equal circles. Electron. J. Comb. 3(32R), 10 (1996) (electronic)

    MathSciNet  Google Scholar 

  8. Lengyel, A., Veres, I.A.: Egységnégyzet lefedése egybevágó körökkel (Covering the unit square with congruent circles). Competition essay, Technical University Budapest, Hungary (1996)

  9. Heppes, A., Melissen, H.: Covering a rectangle with equal circles. Period. Math. Hung. 34, 65–81 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  10. Melissen, J.B.M., Schuur, P.C.: Covering a rectangle with six and seven circles. Discrete Appl. Math. 99, 149–156 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  11. Melissen, H.: Loosest circle coverings of an equilateral triangle. Math. Mag. 70, 119–125 (1997)

    Article  MathSciNet  Google Scholar 

  12. Nurmela, K.J.: Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles. Exp. Math. 9(2), 241–250 (2000)

    MATH  MathSciNet  Google Scholar 

  13. Melissen, H.: Packing and covering with circles. PhD thesis, Universiteit Utrecht, the Netherlands (1997)

  14. Nurmela, K.J., Östergård, P.R.J.: Covering a square with up to 30 circles. Helsinki University of Technology, Laboratory for Theoretical Computer Science. Research report (2000)

  15. Stoyan, Yu.G., Patsuk, V.M.: Covering a polygonal region with equal number of circles of a given radius. Reports Of the National Academy of Sciences of Ukraine, No.  3, pp. 74–77. Kiev (2006) (in Russian)

  16. Patsuk, V., Stoyan, Yu.: Covering a convex polygon with the given number of equal circles of minimal radius. In: Proc. of the Workshop on Cutting Stock Problems 2005 (WSCSP2005), pp. 59–64. Sapientia University of Miercurea-Ciuc, Romania (2006)

    Google Scholar 

  17. Minkowski, H.: Dichteste gitterformige Lagerung. Nachr. Ges. Wiss., pp. 311–355. Gottingen (1904)

  18. Rvatchev, V.L.: Theory of R-functions and Some Applications. Naukova Dumka, Kiev (1982) (in Russian)

    Google Scholar 

  19. Zoutendijk, G.: Methods of Feasible Directions: a Study in Linear and Non-Linear Programming. Elsevier, Amsterdam (1970)

    MATH  Google Scholar 

  20. Voronoi, G.F.: Collected Works, vol. II, pp. 171–368. Academy of Sciences of USSR, Kiev (1952)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute for Mechanical Engineering Problems, National Ukrainian Academy of Sciences, Dm. Pozharsky str. 2/10, Kharkiv, Ukraine

    Y. G. Stoyan & V. M. Patsuk

Authors
  1. Y. G. Stoyan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V. M. Patsuk
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Y. G. Stoyan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Stoyan, Y.G., Patsuk, V.M. Covering a compact polygonal set by identical circles. Comput Optim Appl 46, 75–92 (2010). https://doi.org/10.1007/s10589-008-9191-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-008-9191-8

Keywords

Search

Navigation