COVERING A MAXIMUM NUMBER OF POINTS BY A FIXED NUMBER OF EQUAL DISKS VIA SIMULATED ANNEALING

Simple item page
creativework.keywordscontinuous optimization, disk cover problem, Monte Carlo simulation, stochastic algorithm
creativework.publisherUniversity of Chemical Technology and Metallurgyen
dc.contributor.authorTomova F.
dc.contributor.authorFilipov S.
dc.contributor.authorAvdzhieva A.
dc.date.accessioned2024-07-10T14:27:06Z
dc.date.accessioned2024-07-10T14:51:09Z
dc.date.available2024-07-10T14:27:06Z
dc.date.available2024-07-10T14:51:09Z
dc.date.issued2024-01-01
dc.description.abstractThe presented paper considers the problem of covering a maximum number of n given points in the plane by m equal disks of radius r. A point is covered if it is inside one or more than one disk. The disks need to be placed in the plane in such a way that a maximum number of points are covered. To solve the problem, an objective function, called energy, is introduced in such a way that the greater the covering is, the lower the energy is. Thus, a configuration of disks with minimum energy is a configuration with maximum covering. To find a configuration of disks that minimizes the energy, a stochastic algorithm based on the Monte Carlo simulated annealing technique is proposed. The algorithm overcomes potential local minima, which, as shown in the paper, are quite likely to occur. The computational complexity of the algorithm is O(mn). The algorithm is tested on several cases demonstrating its efficiency in finding global minima of the energy, i.e. configurations with maximum covering.
dc.identifier.doi10.59957/jctm.v59.i2.2024.26
dc.identifier.issn1314-7978
dc.identifier.issn1314-7471
dc.identifier.scopusSCOPUS_ID:85186883179en
dc.identifier.urihttps://rlib.uctm.edu/handle/123456789/922
dc.language.isoen
dc.source.urihttps://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85186883179&origin=inward
dc.titleCOVERING A MAXIMUM NUMBER OF POINTS BY A FIXED NUMBER OF EQUAL DISKS VIA SIMULATED ANNEALING
dc.typeArticle
oaire.citation.issue2
oaire.citation.volume59
Files
Collections
Articles