Mostrar el registro sencillo del ítem

Artículo

dc.creatorBereg, Sergeyes
dc.creatorCabello, S.es
dc.creatorDíaz Báñez, José Migueles
dc.creatorPérez Lantero, Pabloes
dc.creatorSeara Ojea, Carloses
dc.creatorVentura Molina, Inmaculadaes
dc.date.accessioned2018-08-09T11:07:18Z
dc.date.available2018-08-09T11:07:18Z
dc.date.issued2012
dc.identifier.citationBereg, S., Cabello, S., Díaz Báñez, J.M., Pérez Lantero, P., Seara, C. y Ventura Molina, I. (2012). The class cover problem with boxes. Computational Geometry:, 45 (7), 294-304.
dc.identifier.issn0925-7721es
dc.identifier.urihttps://hdl.handle.net/11441/77965
dc.descriptionOpen archive-Elsevieres
dc.description.abstractIn this paper we study the following problem: Given sets R and B of r red and b blue points respectively in the plane, find a minimum-cardinality set H of axis-aligned rectangles (boxes) so that every point in B is covered by at least one rectangle of H, and no rectangle of H contains a point of R. We prove the NP-hardness of the stated problem, and give either exact or approximate algorithms depending on the type of rectangles considered. If the covering boxes are vertical or horizontal strips we give an efficient algorithm that runs in O(r log r + b log b + √ rb) time. For covering with oriented halfstrips an optimal O((r + b) log(min{r, b}))-time algorithm is shown. We prove that the problem remains NP-hard if the covering boxes are half-strips oriented in any of the four orientations, and show that there exists an O(1)-approximation algorithm. We also give an NP-hardness proof if the covering boxes are squares. In this situation, we show that there exists an O(1)-approximation algorithm.es
dc.formatapplication/pdfes
dc.language.isoenges
dc.publisherElsevieres
dc.relation.ispartofComputational Geometry:, 45 (7), 294-304.
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectClass coveres
dc.subjectClassificationes
dc.subjectBoxeses
dc.titleThe class cover problem with boxeses
dc.typeinfo:eu-repo/semantics/articlees
dcterms.identifierhttps://ror.org/03yxnpp24
dc.type.versioninfo:eu-repo/semantics/publishedVersiones
dc.rights.accessRightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Matemática Aplicada II (ETSI)es
dc.relation.publisherversionhttps://www.sciencedirect.com/science/article/pii/S0925772112000375es
dc.identifier.doi10.1016/j.comgeo.2012.01.014es
idus.format.extent11 p.es
dc.journaltitleComputational Geometry:es
dc.publication.volumen45es
dc.publication.issue7es
dc.publication.initialPage294es
dc.publication.endPage304es

FicherosTamañoFormatoVerDescripción
1-s2.0-S0925772112000375-main.pdf280.5KbIcon   [PDF] Ver/Abrir  

Este registro aparece en las siguientes colecciones

Mostrar el registro sencillo del ítem

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Excepto si se señala otra cosa, la licencia del ítem se describe como: Attribution-NonCommercial-NoDerivatives 4.0 Internacional