The largest empty annulus problem
dc.contributor.author
dc.date.accessioned
2018-11-21T10:11:28Z
dc.date.available
2018-11-21T10:11:28Z
dc.date.issued
2003-08-01
dc.identifier.issn
0218-1959
dc.identifier.uri
dc.description.abstract
Given a set of n points S in the Euclidean plane, we address the problem of computing an annulus A, (open region between two concentric circles) of largest width, that partitions S into a subset of points inside and a subset of points outside the circles, such that no point p ∈ S lies in the interior of A. This problem can be considered as a maximin facility location problem for n points such that the facility is a circumference. We give a characterization of the centres of annuli which are locally optimal and we show that the problem can be solved in O(n3 log n) time and O(n) space. We also consider the case in which the number of points in the inner circle is a fixed value k. When k ∈ O(n) our algorithm runs in O(n3 log n) time and O(n) space, furthermore, we can simultaneously optimize for all values of k within the same time bound. When k is small, that is a fixed constant, we can solve the problem in O(n log n) time and O(n) space
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
World Scientific Publishing
dc.relation
MICYT/PN 2001-2004/TIC2001-2392-C03-01
dc.relation.isformatof
Versió postprint del document publicat a: https://doi.org/10.1142/S0218195903001207
dc.relation.ispartof
© International Journal of Computational Geometry and Applications, 2003, vol. 13, núm. 4, p. 317-325
dc.relation.ispartofseries
Articles publicats (D-IMA)
dc.rights
Tots els drets reservats
dc.title
The largest empty annulus problem
dc.type
info:eu-repo/semantics/article
dc.rights.accessRights
info:eu-repo/semantics/openAccess
dc.type.version
info:eu-repo/semantics/acceptedVersion
dc.identifier.doi
dc.identifier.idgrec
001036
dc.contributor.funder
dc.type.peerreviewed
peer-reviewed
dc.identifier.eissn
1793-6357