Rectilinear Crossing Number

來自中國分布式計算總站
跳轉至: 導航搜索
Cleanup icon.png 當前頁面或段落存在質量問題
當前頁面或段落不符合頁面質量要求,使用了不規范的語言或是提供了錯誤的信息,可能誤導讀者,希望了解相關內容的Wiki用戶協助改善。
用戶 cuihao 給出的意見是:沒翻譯 。
其他用戶若有異議,請前往討論:Rectilinear Crossing Number發表見解。
歡迎無wiki賬號的用戶到論壇Wiki系統討論區注冊)參與討論。
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 相關文獻
http://dist.ist.tugraz.at/cape5/rss_main.php 通過 RSS 獲取項目新聞

Rectilinear Crossing Number(通常縮寫為RCN)是由奧地利格拉茨技術大學運作的,基于 BOINC 平臺的分布式計算項目。Rectilinear Crossing Number 的目標是嘗試借助BOINC能召集的計算力來尋找平面化完全圖最小交叉數。目前項目已經得到了階數小于等于17的完全圖的交叉數,還有直到階數為100的完全圖交叉數的一些下界。目前項目正在進行對于18階完全圖的搜索。


如何加入項目

該項目基于 BOINC 平臺,簡要的加入步驟如下(已完成的步驟可直接跳過):

  1. 下載并安裝 BOINC 的客戶端軟件(官方下載頁面程序下載
  2. 點擊客戶端簡易視圖下的“Add Project”按鈕,或高級視圖下菜單中的“工具->加入項目”,將顯示向導對話框
  3. 點擊下一步后在項目列表中找到并單擊選中 Rectilinear Crossing Number 項目(如未顯示該項目,則在編輯框中輸入項目網址:http://dist.ist.tugraz.at/cape5/ ),然后點擊下一步
  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 http://www.ist.tugraz.at/staff/aichholzer/crossings.html.


相關鏈接

官方網站
項目新聞中文翻譯


Boinc Icon.png伯克利開放式網絡計算平臺BOINC
· ·
生命科學類項目 Computational Structural Biology · [email protected] · GPUGRID · Malariacontrol.net · [email protected] (Alpha內測項目)· RNA World · [email protected] · The Lattice Project
地球科學類項目 Climateprediction.net · Quake-Catcher Network Seismic Monitoring
人工智能類項目 [email protected]
天文學項目 Astropulse · [email protected] · [email protected] · [email protected] · [email protected]/AstroPulse Beta (Beta公測項目)· [email protected]
物理化學類項目 [email protected] · [email protected] · Leiden Classical · [email protected] · [email protected]
數學類項目 Collatz Conjecture · [email protected] · primaboinca · PrimeGrid · SZTAKI Desktop Grid · WEP-M+2 Project
密碼類項目 [email protected] · Moo! Wrapper
藝術類項目 BURP
多種應用的項目 [email protected] · World Community Grid · [email protected]
與 BOINC 平臺相關的項目 BOINC Alpha Test · [email protected] · [email protected]
已結束/暫停/合并的項目 [email protected] · AlmereGrid Boinc Grid · [email protected] · [email protected] · BBC Climate Change Experiment · Biochemical Library · [email protected] · [email protected] · [email protected] · CPDN Beta · DepSpid · DistrRTgen · [email protected] · [email protected] · [email protected] · [email protected] · DynaPing · [email protected] · eOn: Long timescale dynamics · [email protected] · Eternity2.fr · [email protected] · Goldbach's Conjecture Project · Ibercivis · [email protected] · [email protected] · [email protected] · MilestoneRSA · [email protected] · [email protected] · NQueens Project · [email protected] · Open Rendering Environment · [email protected] · PicEvolvr.com] · [email protected] · QuantumFIRE alpha · [email protected] ·RamseyX · Rectilinear Crossing Number · Renderfarm.fi · RSA Lattice Siever (2.0) · Seasonal Attribution Project · SHA-1 Collision Search Graz · SIMAP · [email protected] · [email protected] · [email protected] · [email protected] · TANPAKU · Virtual Prairie · Virus Respiratorio Sincitial · XtremLab · Zivis
BOINC 相關的工具 BOINCstats BAM! · BOINC Translation Services · BOINC TThrottle