Finding monochromatic L-shapes in bichromatic point sets

F. Sheikhi, M.T. Berg, de, A. Mohades, M. Davoodi

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

4 Citations (Scopus)


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 languageEnglish
Title of host publicationProceedings of the 22nd Canadian Conference on Computational Geometry (CCCG 2010, Winnipeg MB, Canada, August 9-11, 2010)
PublisherThe CCCG Library
Publication statusPublished - 2010


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

Cite this