### Abstract

Given a set R of red points and a set B of blue points in the plane of total size n, we study the problem of determining all angles for which there exists an L-shape containing all points from B without containing any points from R. We propose an algorithm to solve the problem in O(n^2 log n) time and O(n) storage. We also describe an output-sensitive algorithm that reports all angles in O(n^{5/3+\epsilon} + k log k) time and O(n^{5/3+\epsilon}) storage, where k is the number of reported angular intervals.

Original language | English |
---|---|

Title of host publication | Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010, Winnipeg MB, Canada, August 9-11, 2010) |

Publisher | The CCCG Library |

Pages | 269-272 |

Publication status | Published - 2010 |

## Fingerprint Dive into the research topics of 'Finding monochromatic L-shapes in bichromatic point sets'. Together they form a unique fingerprint.

## Cite this

Sheikhi, F., Berg, de, M. T., Mohades, A., & Davoodi, M. (2010). Finding monochromatic L-shapes in bichromatic point sets. In

*Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010, Winnipeg MB, Canada, August 9-11, 2010)*(pp. 269-272). The CCCG Library.