Separating bichromatic point sets by L-shapes

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

doi:10.1016/j.comgeo.2015.06.008

Separating bichromatic point sets by L-shapes

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

Research output: Contribution to journal › Article › Academic › peer-review

15 Citations (Scopus)

244 Downloads (Pure)

Abstract

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

Original language	English
Pages (from-to)	673-687
Journal	Computational Geometry
Volume	48
Issue number	9
DOIs	https://doi.org/10.1016/j.comgeo.2015.06.008
Publication status	Published - 2015

Access to Document

10.1016/j.comgeo.2015.06.008

publishers versionFinal published version, 915 KBLicence: TAVERNE

Cite this

@article{e6567d7e092c4c1ea43c4c923feea543,

title = "Separating bichromatic point sets by L-shapes",

abstract = "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\textasciicircum{}\{8/5+e\} +klogk) time and O(n\textasciicircum{}\{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",

author = "F. Sheikhi and \{Berg, de\}, M.T. and A. Mohades and M. Davoodi",

year = "2015",

doi = "10.1016/j.comgeo.2015.06.008",

language = "English",

volume = "48",

pages = "673--687",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier B.V.",

number = "9",

}

TY - JOUR

T1 - Separating bichromatic point sets by L-shapes

AU - Sheikhi, F.

AU - Berg, de, M.T.

AU - Mohades, A.

AU - Davoodi, M.

PY - 2015

Y1 - 2015

N2 - 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

AB - 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

U2 - 10.1016/j.comgeo.2015.06.008

DO - 10.1016/j.comgeo.2015.06.008

M3 - Article

SN - 0925-7721

VL - 48

SP - 673

EP - 687

JO - Computational Geometry

JF - Computational Geometry

IS - 9

ER -

Separating bichromatic point sets by L-shapes

Abstract

Access to Document

Fingerprint

Cite this