Rectilinear Crossing Number

http://dist.ist.tugraz.at/cape5/

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.

详细的见http://dist.ist.tugraz.at/cape5/why.html



[ Last edited by Youth on 2006-7-26 at 19:41 ]

怎么有两个小组啊~~~
Youth和wenmao要协调一下~~~

其实这个项目就是说：在欧氏平面上有n个点，每三点不共线，如果每两个点之间连上一条线段的话，至少会有几个交点？
这个据说在运输问题中有用~~~
大家还记得K5不是平面图吧，也就是说，n=5的时候开始有交点。

有没有搞错啊~~~刚去注册了账户~~~填了Profile~~~然后就变成User of the day了~~~
是运气还是Bug~~~存疑当中~~~

呵呵，fwjmath是今日之星啊！
Youth建的team似乎应该叫RCN@China.

呵呵，我一般会先搜索一下有没有包含china的团队名的：）

我加了wenmao的那一个，你的“RCU”缩写得也太不厚道了~~~

呵呵，那天太粗心了...

试了下这个项目, 占用内存少, 2.7+1.3M, 占用空间也很少 <400KB
不过有个问题, 就是一个任务完成后有11个数据要上传, 但是任务完成得太快了, 很多都是几秒.. 这样就积压大量结果数据等待上传, 而这个时候 boinc.exe 就会消耗相当大量的cpu, 很浪费的说
不知道大家有没有这个情况?

是这个样子~~~我还死机了一次~~~
但是也有的WU是比较长的，所以平均下来可能跟以前有优化的SZDG差不多~~~

项目新闻：
August 30, 2006
Please abort all RCN workunits now. Due to recent database trouble their parameters are messy. You don't need to report them because I had to delete them all. Don't worry about your credits. Generous credits will be given to all users who had work in progress.

请放弃有关RCN WU不要再运算
看来有许多有关 RCN WU结果被删除, 与DB的一些"字串"问题有关 .不过不影响 credits 积分

August 27, 2006
After some days of maintenance our server is online again. Everything should work properly now.


August 25, 2006
We have some trouble with our server. See 'Message boards : Radio RCN'. Can we fix it? Yes we can. I will try to do that tomorrow in the morning. Bernhard.

August 22, 2006
We will have some intervals of downtime today.

August 21, 2006
Maintenance Jobs: If there are still *old* workunits on your clients, please abort them now. 'Old' means workunits that have to be computed with the old 'cape-crossing' application instead of the new 'tcape-crossing' application. We will delete them from the database very soon and can not grant credits afterwards.

以上说明如果有任务包未完成请舍弃WU(包), 影可能是运算程式要改版..不support 旧版任务包(WU)


August 07, 2006
We have a new scientific application. It enforces a time limit for our workunits. Currently the limit is set to 2 hours. But note that we measure the real cpu time. For P4's with HT and two processes in parallel the maximum running time will be doubled and also other processes at the computer may stretch the maximum running time.

August 07, 2006
The winner of our logo contest is Cori. Congratulations, you did a great job!

August 01, 2006
Our users contributed some very good designs for a project logo. Now you can vote for your favourite one, see 'Message boards : Radio RCN '. And another thing: We started 4 weeks ago and now we have more than 1 000 participating hosts. This is by far more than we expected and we are very proud of the project's success. Time to say THANK YOU!

July 22, 2006
Logo contest officially started, see 'Message boards : Radio RCN : Project logo'. In a few minutes we will have 10 000 new workunits and additionally I will insert another big bunch of wu's tomorrow.

8一下RCN的得分制度：
最近SETI没有WU算，就找了RCN做替代项目。RCN是提交立即得分、根据CPU时间给分，跟很早以前的ROSETTA很像，也跟我很早以前装的Crunch3r的5.5.0版优化BOINC很合拍。
但是（请注意），并非优化的越好得分越多，只要申请分大于（CPU时间×0.007），则最终得分一律降为（CPU时间×0.006），这样就不会出现得分成百上千的超BT狂了。
根据本人的测试，LINUX下XEON2.4GHZ×2的优化结果已经接近这个警戒线了，再好的机器优化都是浪费。如果优化的结果使申请分介于（CPU时间×0.006）和（CPU时间×0.007）之间，那么恭喜你，你已经得到了再好的机器也得不到的高分了！

不過怎麼沒貼最新的消息?
據他們說好像要推出checkpoint和進度條的機制....
不用再猜現在算的工作是小還是大了...
有時候以為算的只有幾秒就會上傳,
結果一等等了快2小時...

这个估计还要等一下~~~
新闻的话迟一点我放到置顶帖吧~~~

May 16, 2007
We have another 111 000 wednesday workunits. They are called W2 and they are the same as the W1's but we have increased the maximum running time to 8 hours per workunit for all CPU types. Note that we have checkpointing now and you won't lose your credit if you need to reboot your machine.

新WU发布，命名W2，最大运行时间8小时。已经增加了进度显示和检查点，这样重起机器后就不会丢失未算完的进度。