Rectilinear Crossing Number

Zhouxiaobo讨论 | 贡献2017年12月6日 (三) 21:18的版本 (已结束。)
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)
跳转至: 导航搜索
Cleanup icon.png 当前页面或段落存在质量问题
用户 cuihao 给出的意见是:没翻译 。
其他用户若有异议,请前往讨论:Rectilinear Crossing Number发表见解。
Rectilinear Crossing Number
Rectilinear Crossing Number logo
Rectilinear Crossing Number logo
Rectilinear Crossing Number 运行中的图形界面
Rectilinear Crossing Number 运行中的图形界面
开发者 奥地利格拉茨技术大学Austria.gif
版本历史 2006年6月30日
计算程序 WindowsLinuxMac OS X
项目平台 BOINC 平台
项目类别 数学
项目状态 已结束
官方网址 Rectilinear Crossing Number
项目文献 分类:Rectilinear Crossing Number 相关文献 通过 RSS 获取项目新闻

Rectilinear Crossing Number(通常缩写为RCN)是由奥地利格拉茨技术大学运作的,基于 BOINC 平台的分布式计算项目。Rectilinear Crossing Number 的目标是尝试借助BOINC能召集的计算力来寻找平面化完全图最小交叉数。目前项目已经得到了阶数小于等于17的完全图的交叉数,还有直到阶数为100的完全图交叉数的一些下界。目前项目正在进行对于18阶完全图的搜索。


该项目基于 BOINC 平台,简要的加入步骤如下(已完成的步骤可直接跳过):

  1. 下载并安装 BOINC 的客户端软件(官方下载页面程序下载
  2. 点击客户端简易视图下的“Add Project”按钮,或高级视图下菜单中的“工具->加入项目”,将显示向导对话框
  3. 点击下一步后在项目列表中找到并单击选中 Rectilinear Crossing Number 项目(如未显示该项目,则在编辑框中输入项目网址: ),然后点击下一步
  4. 输入您可用的电子邮件地址,并设置您在该项目的登录密码(并非您的电子邮件密码)
  5. 再次点击下一步,如项目服务器工作正常(并且有适合自身操作系统的计算程序),即已成功加入项目

更详细的加入方法说明,请访问 BOINC 新手指南BOINC 使用教程

本站推荐您加入 Team China 团队,请访问项目官方网站的 团队检索页面,搜索(Search)并进入 Team China 的团队页面,点击页面中的 Join 并输入用户登录信息即可加入!


在图论,交叉数是指一个图在平面上,边的交叉点的最小数目。一个图在平面上可以有多种画法,若有多于两条边相交于同一点,每对相交边计算一次。给定一个图,计算其交叉数是一个NP-hard的问题。Rectilinear Crossing Number 想要解决的就是这个问题的一个特殊情况,也就是当图为完全图时候的情况。目前项目已经得到了阶数小于等于17的完全图的交叉数,还有直到阶数为100的完全图交叉数的一些下界,详细的结果请参看这里(英文)

What is the Rectilinear Crossing Number Project?

Many questions in computational and combinatorial geometry are based on finite sets of points in the Euclidean plane. Several problems from graph theory also fit into this framework, when edges are restricted to be straight. A typical question is the prominent problem of the rectilinear crossing number (related to transport problems and optimization of print layouts for instance): What is the least number of crossings a straight-edge drawing of the complete graph on top of a set of n points in the plane obtains? Here complete graph means that any pair of points is connected by a straight-edge. Moreover we assume general position for the points, i.e., no three points lie on a common line.

It is not hard to see that we can place four points in a way so that no crossing occurs. For five points the drawing shows different ways to place them (these are all different order types (introduced by Goodman and Pollack in 1983)). If you place five points in convex positions then there are five crossings. The best you can do is to get only one crossing (there is no way to draw a complete graph on five points without crossings, even if you allow the edges to be curves). BTW: Maximizing the number of crossings is easy: Just place all n points on a circle to get the maximum of n choose 4 crossings. crossings.gif

For larger point sets it is very hard to determine the best configuration. The main reason is that the number of combinatorially different ways to place those points grows exponentially. For example already for n=11 there are 2,334,512,907 different configurations.

The remarkable hunt for crossing numbers of the complete graph has been initiated by R. Guy in the 1960s. Till the year 2000 only values for n<=9 have been found, in 2001 n=10 was solved and the case n=11 was settled in 2004. The main goal of the current project is to use sophisticated mathematical methods (abstract extension of order types) to determine the rectilinear crossing number for small values of n. So far we have been successful for n <= 17. From very recent (not even published yet) mathematical considerations the rectilinear crossing numbers for n=19 and n=21 are also known. So the most tantalizing problem now is to determine the true value for n=18, which is the main focus of this project.

An updated list for the best point sets known so far can be found at



Boinc Icon.png伯克利开放式网络计算平台BOINC
· ·
生命科学类项目 Computational Structural Biology · DrugDiscovery@Home · GPUGRID · · RALPH@home (Alpha内测项目)· RNA World · Rosetta@home · The Lattice Project
地球科学类项目 · Quake-Catcher Network Seismic Monitoring
人工智能类项目 MindModeling@Home
天文学项目 Astropulse · Cosmology@Home · MilkyWay@home· Asteroids@home
物理化学类项目 Einstein@Home · Hydrogen@Home · Leiden Classical · LHC@home · QMC@Home
数学类项目 Collatz Conjecture · NFS@Home · primaboinca · PrimeGrid · SZTAKI Desktop Grid · WEP-M+2 Project
密码类项目 Moo! Wrapper
艺术类项目 BURP
游戏类项目 暂无活跃项目
多种应用的项目 World Community Grid · Yoyo@home · Charity Engine
与 BOINC 平台相关的项目 BOINC Alpha Test · Pirates@home · WUProp@Home
已结束/暂停/合并的项目 Enigma@Home · CAS@home · ABC@home · AlmereGrid Boinc Grid · APS@Home · AQUA@home · BBC Climate Change Experiment · Biochemical Library · BRaTS@Home · Cels@Home · Chess960@Home · CPDN Beta · DepSpid · DistrRTgen · DNA@home · DNETC@HOME · Docking@Home · Drug@Home · DynaPing · EDGeS@Home · eOn: Long timescale dynamics · Evo@home · · FreeHAL@home · Goldbach's Conjecture Project · Ibercivis · Magnetism@home · Mersenne@home · MilestoneRSA · Minecraft@Home · Mopac@home · MFluids@Home · Nano-Hive@home · NQueens Project · Orbit@Home · Open Rendering Environment · POEM@HOME ·] · Predictor@home · QuantumFIRE alpha · Ramsey@Home ·RamseyX · Rectilinear Crossing Number · · RSA Lattice Siever (2.0) · Seasonal Attribution Project · SHA-1 Collision Search Graz · SIMAP · SLinCA@Home · Spinhenge@home · Sudoku@vtaiwan · Superlink@Technion · TANPAKU · Virtual Prairie · Virus Respiratorio Sincitial · XtremLab · Zivis · SETI@home · SETI@home/AstroPulse Beta (Beta公测项目)
BOINC 相关的工具 BOINCstats BAM! · BOINC Translation Services · BOINC TThrottle