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

3 Citations (Scopus)

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 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
Pages269-272
Publication statusPublished - 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.