Stabbers of line segments in the plane

• M. Claverol ^[1] ; D. Garijo ^[2] ; C.I. Grima ^[2] ; A. Márquez ^[2] ; C. Seara ^[1]
  1. [1] Universitat Politècnica de Catalunya

     Universitat Politècnica de Catalunya

     Barcelona, España

     
  2. [2] Universidad de Sevilla

     Universidad de Sevilla

     Sevilla, España

     
• Localización: XIII Encuentros de Geometría Computacional: Zaragoza, del 29 de junio al 1 de julio de 2009 / Alfredo García Olaverri (ed. lit.) , Javier Tejel Altarriba (ed. lit.) , 2009, ISBN 978-84-92774-11-1, págs. 269-275
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • The problem of computing a representation of the stabbing lines of a set S of n line segments in the plane was solved by Edelsbrunner et al. with an (n log n) time and O(n) space algorithm. We present a study of different types of stabbers such as wedges, double-wedges, 2-level trees, and zigzags; providing efficient algorithms whose time and space complexities depend on the number of combinatorially different extreme lines hS or critical lines cS, and the number kS of different slopes that appear in S.