Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Stabbing segments with rectilinear objects

Autor
Claverol, M.; Garijo, D.; Korman, M.; Seara, C.; Silveira, R.I.
Tipus d'activitat
Article en revista
Revista
Applied mathematics and computation
Data de publicació
2017-09-15
Volum
309
Pàgina inicial
359
Pàgina final
373
DOI
https://doi.org/10.1016/j.amc.2017.04.001 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/104941 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0096300317302369 Obrir en finestra nova
Resum
Given a set S of n line segments in the plane, we say that a region R ¿ R 2 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 rect...
Paraules clau
Computational Geometry, Algorithms, Line Segments, Stabbing Problems, Classification Problems
Grup de recerca
DCCG - Grup de recerca en geometria computacional, combinatoria i discreta

Participants