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

Reporting Bichromatic Segment Intersections from Point Sets


Advanced Search
Opened Access Reporting Bichromatic Segment Intersections from Point Sets

Show item statistics
Export to
Author: 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
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2012
Published in: International Journal of Computational Geometry & Applications, 22 (5), 421-437.
Document type: Article
Abstract: 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.
Size: 263.1Kb
Format: PDF


DOI: 10.1142/S0218195912500100

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)