Separating bichromatic point sets by L-shapes

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

7 Citaten (Scopus)

Samenvatting

Given a set R of red points and a set B of blue points in the plane, we study the problem of determining all angles for which there exists an L-shape containing all points from B and no points from R . We propose a worst-case optimal algorithm to solve this problem in O(n2) time and O(n) storage, where n=|R|+|B|. We also describe an output-sensitive algorithm that reports these angles in O(n^{8/5+e} +klogk) time and O(n^{8/5+e}) storage, where k is the number of reported angular intervals and e>0 is any fixed constant. Keywords: Separability; Bichromatic point sets; L-shape
Originele taal-2Engels
Pagina's (van-tot)673-687
TijdschriftComputational Geometry
Volume48
Nummer van het tijdschrift9
DOI's
StatusGepubliceerd - 2015

Vingerafdruk Duik in de onderzoeksthema's van 'Separating bichromatic point sets by L-shapes'. Samen vormen ze een unieke vingerafdruk.

Citeer dit