Bichromatic lines in the plane

Michael S. Payne

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Given a set of red and blue points in the plane, a bichromatic line is a line containing at least one red and one blue point. We prove the following conjecture of Kleitman and Pinchasi. Let P be a set of n red, and n or n-1 blue points in the plane. If neither color class is collinear, then P determines at least |P| - 1 bichromatic lines. In fact we are able to achieve the same conclusion under the weaker assumption that P is not collinear or a near-pencil.

Original languageEnglish
Pages (from-to)857-864
Number of pages8
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number2
DOIs
Publication statusPublished - 2017

Keywords

  • Bichromatic lines
  • Colored point configurations
  • Discrete geometry

Cite this