Rectilinear Crossing Number

Rectilinear Crossing Number je matematický projekt, ktorý sa snaží vyriešiť rôzne výpočtové a kombinačné problémy vychádzajúce z konečného počtu bodov v Euklidovej rovine.

Sem patrí niekoľko problémov z teórie grafov, v ktorých spojnice medzi akýmikoľvek dvoma bodmi sú priame (pod pojmom graf v tomto prípade rozumieme abstraktné znázornenie skupiny objektov, kde niektoré z nich sú navzájom spojené).

Základná otázka znie: aký je najmenší počet priesečníkov v grafe, ktorý vznikol vzájomným prepojením všetkých n bodov v rovine priamymi spojnicami? Uvažujeme všeobecné rozloženie bodov v rovine, kde tri rôzne body neležia na jednej priamke.