Artículo
Reporting Bichromatic Segment Intersections from Point Sets
Autor/es | Cortés Parejo, María del Carmen
Garijo Royo, Delia Garrido Vizuete, María de los Angeles Grima Ruiz, Clara Isabel Márquez Pérez, Alberto Moreno González, Auxiliadora Valenzuela Muñoz, Jesús Villar Liñán, María Trinidad |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2012 |
Fecha de depósito | 2016-03-17 |
Publicado en |
|
Resumen | In this paper, we introduce a natural variation of the problem of computing all bichromatic intersections between two sets of segments. Given two sets R and B of n points in the plane defining two sets of segments, say red ... In this paper, we introduce a natural variation of the problem of computing all bichromatic intersections between two sets of segments. Given two sets R and B of n points in the plane defining two sets of segments, say red and blue, we present an O(n2) time and space algorithm for solving the problem of reporting the set of segments of each color intersected by segments of the other color. We also prove that this problem is 3-Sum hard and provide some illustrative examples of several point configurations. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Reporting bichromatic.pdf | 263.1Kb | [PDF] | Ver/ | |