Artículo
Stabbing segments with rectilinear objects
Autor/es | Claverol Aguas, Mercé
Garijo Royo, Delia Korman, Matias Seara Ojea, Carlos Silveira Isoba, Rodrigo Ignacio |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2017 |
Fecha de depósito | 2019-05-27 |
Publicado en |
|
Resumen | 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 ... 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). |
Identificador del proyecto | FQM-0164
MTM2014-60127-P |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
1703.04329.pdf | 446.7Kb | [PDF] | Ver/ | |