Repositorio de producción científica de la Universidad de Sevilla

Covering point sets with two disjoint disks or squares


Advanced Search

Show simple item record

dc.creator Cabello, Sergio es
dc.creator Díaz Báñez, José Miguel es
dc.creator Seara Ojea, Carlos es
dc.creator Sellarés, J. Antoni es
dc.creator Urrutia, Jorge es
dc.creator Ventura Molina, Inmaculada es 2018-08-09T08:54:29Z 2018-08-09T08:54:29Z 2007
dc.identifier.citation Cabello, S., Díaz Báñez, J.M., Seara, C., Sellarés, J.A., Urrutia, J. y Ventura Molina, I. (2007). Covering point sets with two disjoint disks or squares. Computational Geometry, 40 (3), 195-206.
dc.identifier.issn 0925-7721 es
dc.description Open archive-Elsevier es
dc.description.abstract We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks CR and CB with disjoint interiors such that the number of red points covered by CR plus the number of blue points covered by CB is maximized. We give an algorithm to solve this problem in O(n8/3 log2 n) time, where n denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares SR and SB instead of unit disks can be solved in O(nlog n) time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using O(n3 log n) time. es
dc.format application/pdf es
dc.language.iso eng es
dc.publisher Elsevier es
dc.relation.ispartof Computational Geometry, 40 (3), 195-206.
dc.rights Attribution-NonCommercial-NoDerivatives 4.0 Internacional *
dc.rights.uri *
dc.subject Covering es
dc.subject Facility location es
dc.subject Geometric optimization es
dc.title Covering point sets with two disjoint disks or squares es
dc.type info:eu-repo/semantics/article es
dc.type.version info:eu-repo/semantics/publishedVersion es
dc.rights.accessrights info:eu-repo/semantics/openAccess es
dc.contributor.affiliation Universidad de Sevilla. Departamento de Matemática Aplicada II (ETSI) es
dc.relation.publisherversion es
dc.identifier.doi 10.1016/j.comgeo.2007.10.001 es
idus.format.extent 12 p. es
dc.journaltitle Computational Geometry es
dc.publication.volumen 40 es
dc.publication.issue 3 es
dc.publication.initialPage 195 es
dc.publication.endPage 206 es
Size: 681.4Kb
Format: PDF

This item appears in the following Collection(s)

Show simple item record