Hi,

LetRbe a set ofnred points in the plane, and a letBbe a set ofn

blue points in the plane. We call a line LaseparatorforRandBif Lhas all points ofRto

one side and all points ofBto the other side.

I need to find a randomized algorithm that can decide

inO(n) expected time whetherRandBhave a separator.

Any idea please?