To access the full text documents, please follow this link: http://hdl.handle.net/2117/104941
| dc.contributor | Universitat Politècnica de Catalunya. Departament de Matemàtiques |
|---|---|
| dc.contributor | Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
| dc.contributor.author | Claverol Aguas, Mercè |
| dc.contributor.author | Garijo Royo, Delia |
| dc.contributor.author | Korman, Matias |
| dc.contributor.author | Seara Ojea, Carlos |
| dc.contributor.author | Silveira, Rodrigo Ignacio |
| dc.date | 2017-09-15 |
| dc.identifier.citation | Claverol, M., Garijo, D., Korman, M., Seara, C., Silveira, R.I. Stabbing segments with rectilinear objects. "Applied mathematics and computation", 15 Setembre 2017, vol. 309, p. 359-373. |
| dc.identifier.citation | 0096-3003 |
| dc.identifier.citation | 10.1016/j.amc.2017.04.001 |
| dc.identifier.uri | http://hdl.handle.net/2117/104941 |
| 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 different stabbers for several shapes of stabbers. Specifically, 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(nlog¿n) (for strips, quadrants, and 3-sided rectangles), and O(n2log¿n) (for rectangles). |
| dc.language.iso | eng |
| dc.relation | http://www.sciencedirect.com/science/article/pii/S0096300317302369 |
| dc.rights | info:eu-repo/semantics/openAccess |
| dc.subject | Àrees temàtiques de la UPC::Matemàtiques i estadística |
| dc.subject | Computational geometry |
| dc.subject | Algorithms |
| dc.subject | Computational geometry |
| dc.subject | Algorithms |
| dc.subject | Line segments |
| dc.subject | Stabbing problems |
| dc.subject | Classification problems |
| dc.subject | Geometria computacional |
| dc.subject | Algorismes |
| dc.subject | Classificació AMS::68 Computer science::68W Algorithms |
| dc.title | Stabbing segments with rectilinear objects |
| dc.type | info:eu-repo/semantics/submittedVersion |
| dc.type | info:eu-repo/semantics/article |
Related documents
Other documents of the same author
Claverol Aguas, Mercè; Garijo, Delia; Korman, Matias; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio
Claverol Aguas, Mercè; García, Alfredo; Garijo Royo, Delia; Seara Ojea, Carlos; Tejel, Javier
Bereg, Sergey; Hurtado Díaz, Fernando Alfredo; Kano, Mikio; Korman, Matias; Lara, Dolores; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio; Urrutia Galicia, Jorge; Verbeek, Kevin
Claverol Aguas, Mercè; Seara Ojea, Carlos; Garijo, Delia; Korman, M.; Silveira, Rodrigo Ignacio
Garijo Royo, Delia; Marquez Pérez, Alberto; Rodríguez, Natalia; Silveira, Rodrigo Ignacio