Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/21700

Stabbing Segments with Rectilinear Objects
Claverol Aguas, Mercè; Seara Ojea, Carlos; Garijo, Delia; Korman, M.; Silveira, Rodrigo Ignacio
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
Given a set of n line segments in the plane, we say that a region R of the plane is a stabber if R contains exactly one end point of each segment of the set. In this paper we provide efficient algorithms for determining wheter or not a stabber exists for several shapes of stabbers. Specially, we consider the case in which the stabber can be described as the intersecction of isothetic halfplanes (thus the stabbers are halfplanes, strips, quadrants, 3-sided rectangles, or rectangles). We provided efficient algorithms reporting all combinatorially different stabbers of the shape. The algorithms run in O(n) time (for the halfplane case), O(n logn) time (for strips and quadrants), O(n^2) (for 3-sided rectangles), or O(n^3) time (for rectangles).
Àrees temàtiques de la UPC::Matemàtiques i estadística::Àlgebra
Geometry, Differential
Àlgebra lineal
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
         

Mostra el registre complet del document

Documents relacionats

Altres documents del mateix autor/a

Claverol Aguas, Mercè; Garijo, Delia; Grima, Clara; Márquez, Alberto; Seara Ojea, Carlos
Claverol Aguas, Mercè; Garijo, Delia; Hurtado Díaz, Fernando Alfredo; Lara Cuevas, María Dolores; Seara Ojea, Carlos
Cáceres, Jose; Garijo, Delia; Puertas González, María Luz; Seara Ojea, Carlos
Abellanas, Manuel; Claverol Aguas, Mercè; Hernández-Peñalver, Gregorio; Hurtado Díaz, Fernando Alfredo; Sacristán Adinolfi, Vera; Saumell Mendiola, Maria; Silveira, Rodrigo Ignacio
Díaz Bañez, José Miguel; Korman Cozzetti, Matías; Pérez Lantero, Pablo; Pilz, Alexander; Seara Ojea, Carlos; Silveira, Rodrigo Ignacio