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 |
dc.date.accessioned | 2018-08-09T08:54:29Z | |
dc.date.available | 2018-08-09T08:54:29Z | |
dc.date.issued | 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.identifier.uri | https://hdl.handle.net/11441/77941 | |
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 | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
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 |
dcterms.identifier | https://ror.org/03yxnpp24 | |
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 | https://www.sciencedirect.com/science/article/pii/S0925772107001034 | 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 |