dc.creator | Claverol Aguas, Mercé | es |
dc.creator | Garijo Royo, Delia | es |
dc.creator | Korman, Matias | es |
dc.creator | Seara Ojea, Carlos | es |
dc.creator | Silveira Isoba, Rodrigo Ignacio | es |
dc.date.accessioned | 2019-05-27T11:34:49Z | |
dc.date.available | 2019-05-27T11:34:49Z | |
dc.date.issued | 2017 | |
dc.identifier.citation | Claverol Aguas, M., Garijo Royo, D., Korman, M., Seara Ojea, C. y Silveira Isoba, R.I. (2017). Stabbing segments with rectilinear objects. Applied Mathematics and Computation, 309 (september 2017), 359-373. | |
dc.identifier.issn | 0096-3003 | es |
dc.identifier.uri | https://hdl.handle.net/11441/86855 | |
dc.description.abstract | Given a set S of n line segments in the plane, we say that a region R R2 is a
stabber for S if R contains exactly one endpoint of each segment of S. In this paper we provide
optimal or near-optimal algorithms for reporting all combinatorially di erent stabbers for
several shapes of stabbers. Speci cally, we consider the case in which the stabber can be
described as the intersection of axis-parallel halfplanes (thus the stabbers are halfplanes,
strips, quadrants, 3-sided rectangles, or rectangles). The running times are O(n) (for the
halfplane case), O(n log n) (for strips, quadrants, and 3-sided rectangles), and O(n2 log n)
(for rectangles). | es |
dc.description.sponsorship | Junta de Andalucía PAI FQM-0164 | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad MTM2014-60127-P | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Applied Mathematics and Computation, 309 (september 2017), 359-373. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights | Attribution-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nd/4.0/ | * |
dc.subject | Computational geometry | es |
dc.subject | Algorithms | es |
dc.subject | Line segments | es |
dc.subject | Stabbing problems | es |
dc.subject | Classification problems | es |
dc.title | Stabbing segments with rectilinear objects | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.relation.projectID | FQM-0164 | es |
dc.relation.projectID | MTM2014-60127-P | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0096300317302369 | es |
dc.identifier.doi | 10.1016/j.amc.2017.04.001 | es |
dc.contributor.group | Universidad de Sevilla. FQM164: Matemática Discreta: Teoría de Grafos y Geometría Computacional | es |
idus.format.extent | 19 | es |
dc.journaltitle | Applied Mathematics and Computation | es |
dc.publication.volumen | 309 | es |
dc.publication.issue | september 2017 | es |
dc.publication.initialPage | 359 | es |
dc.publication.endPage | 373 | es |
dc.identifier.sisius | 21151581 | es |