Repositorio de producción científica de la Universidad de Sevilla

Reporting Bichromatic Segment Intersections from Point Sets

Opened Access Reporting Bichromatic Segment Intersections from Point Sets

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: 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: 2012
Publicado en: International Journal of Computational Geometry & Applications, 22 (5), 421-437.
Tipo de documento: Artículo
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 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.
Tamaño: 263.1Kb
Formato: PDF

URI: http://hdl.handle.net/11441/38750

DOI: 10.1142/S0218195912500100

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones