Al Piskun: first light

2026-07-02T10:40:47Z

first light

New page

{{Infobox software
| name = Rectilinear Crossing Number Project
| logo = Rcnlogo.png
| logo caption = Project logo
| screenshot =
| caption =
| description = The Rectilinear Crossing Number Project (also known as cape5 or RCN) was a completed BOINC volunteer computing project run by Graz University of Technology that used distributed computing to help determine the rectilinear crossing number of the complete graph K18.
| status = Completed
| category = Mathematics
| compute = CPU
| dependencies = None
| developer = Institute for Software Technology, [[wikipedia:Graz University of Technology|Graz University of Technology]]
| author = Oswin Aichholzer
| sponsor = Graz University of Technology
| maintainer =
| released = {{Start date and age|2006|07|25}}
| completed = Yes
| discontinued =
| repository =
| programming language =
| operating system = Windows, Linux
| size =
| stats as of =
| average performance =
| active users =
| total users =
| active hosts =
| total hosts =
| rac =
| credit per day =
| gpu performance =
| cpu performance =
| website = {{URL|http://dist.ist.tugraz.at/cape5}}
| license =
}}

'''Rectilinear Crossing Number Project''' (internally referred to by its developers as '''cape5''', and often abbreviated '''RCN''' or '''RCP''') was a [[BOINC]] volunteer computing project in [[wikipedia:computational geometry|computational geometry]] operated by the Institute for Software Technology at [[wikipedia:Graz University of Technology|Graz University of Technology]] in Austria. The project asked volunteers' computers to search for optimal straight-line drawings of complete graphs in order to help settle open cases of the rectilinear crossing number problem, a long-standing question in combinatorics first raised by [[wikipedia:Richard K. Guy|Richard K. Guy]] in the 1960s.<ref>{{Cite web |title=Applications |url=http://dist.ist.tugraz.at/cape5/apps.php |publisher=Institute for Software Technology, Graz University of Technology |access-date=2026-07-01}}</ref><ref>{{Cite web |title=The Rectilinear Crossing Number Project: Why? |url=http://dist.ist.tugraz.at/cape5/why.html |publisher=Institute for Software Technology, Graz University of Technology |access-date=2026-07-01}}</ref>

The project was announced by BOINC founder David Anderson on 25 July 2006, alongside two other new BOINC-based projects, [[wikipedia:Riesel Sieve|Riesel Sieve]] and [[wikipedia:Spinhenge@home|Spinhenge@home]].<ref name="boincnews">{{Cite web |title=Welcome to three new BOINC-based projects |url=https://boinc.berkeley.edu/forum_thread.php?id=5108 |publisher=BOINC |first=David |last=Anderson |date=2006-07-25 |access-date=2026-07-01}}</ref>

== The mathematical problem ==
A '''rectilinear drawing''' of a graph places each vertex at a point in the plane, in general position (no three points collinear), and represents each edge as a straight line segment. The '''rectilinear crossing number''' of a graph <math>G</math>, denoted <math>\overline{cr}(G)</math>, is the minimum possible number of pairs of crossing edges over all such drawings.<ref name="mathworld">{{Cite web |title=Rectilinear Crossing Number |url=https://mathworld.wolfram.com/RectilinearCrossingNumber.html |publisher=Wolfram MathWorld |access-date=2026-07-01}}</ref>

For the [[wikipedia:complete graph|complete graph]] <math>K_n</math>, computing <math>\overline{cr}(K_n)</math> is equivalent to finding a set of <math>n</math> points in the plane, in general position, that minimizes the number of convex quadrilaterals formed by the points.<ref name="mathworld" /> Exact values were known only for small <math>n</math> for decades; determining <math>\overline{cr}(K_n)</math> for larger <math>n</math> is [[wikipedia:NP-hardness|NP-hard]] to decide against a fixed target, and the number of possible point configurations grows explosively with <math>n</math>, making the problem well suited to distributed search.<ref name="mathworld" />

Progress on the problem before the BOINC project was slow: only values up to <math>n = 9</math> were known before 2000, <math>n = 10</math> was settled in 2001, and <math>n = 11</math> in 2004, using a technique called abstract order type extension developed by Aichholzer, Aurenhammer and Krasser.<ref name="why">{{Cite web |title=The Rectilinear Crossing Number Project |url=http://dist.ist.tugraz.at/cape5/why.html |publisher=Institute for Software Technology, Graz University of Technology |access-date=2026-07-01}}</ref> By the time the same method had pushed the known range up to <math>n \le 17</math>, and had also produced (not-yet-published) results for <math>n = 19</math> and <math>n = 21</math>, the case <math>n = 18</math> remained the most tantalizing unsolved instance, and became the specific target of the BOINC project.<ref name="why" />

== History ==
The rectilinear crossing number project, nicknamed "cape5" after the server directory in which it was hosted (<code>dist.ist.tugraz.at/cape5</code>), was developed by the Institute for Software Technology at Graz University of Technology and built on prior mathematical work by Oswin Aichholzer, Franz Aurenhammer and Hannes Krasser.<ref name="why" /><ref>{{Cite journal |last1=Aichholzer |first1=O. |last2=Aurenhammer |first2=F. |last3=Krasser |first3=H. |title=On the Crossing Number of Complete Graphs |journal=Computing |volume=76 |issue=1-2 |pages=165-176 |year=2006 |doi=10.1007/s00607-005-0133-3}}</ref> The project distributed workunits, dubbed "cape-crossing" jobs, that tested candidate point configurations for the complete graph K18, aiming to prove that no configuration could beat the best drawings already found by other means.<ref>{{Cite web |title=Rectilinear Crossing Number (RCN) - beendet |url=https://www.bc-team.org/viewtopic.php?p=951 |publisher=BOINC Confederation Team |access-date=2026-07-01 |language=de}}</ref>

Volunteer participation grew quickly after launch. By mid-2007 the project reported issuing over 525,000 workunits for a single generation of the search, and its community had reached a combined output of roughly three CPU-years of computation in a single day.<ref name="bcteam">{{Cite web |title=Rectilinear Crossing Number (RCN) - beendet |url=https://www.bc-team.org/viewtopic.php?p=951 |publisher=BOINC Confederation Team |date=2007-06-23 |access-date=2026-07-01 |language=de}}</ref> Some individual workunits ran for exceptionally long periods on volunteers' machines, with one participant reporting a single completed workunit that had run for 542 hours.<ref name="bcteam" /> The project's success led the team to acquire a second dedicated server, which they intended to reuse for a planned successor project, provisionally named "SUDOKU," that would search for the smallest possible starting configuration of the puzzle; it is not confirmed whether this successor project was ultimately released.<ref name="bcteam" />

In January of a later year the project introduced a second, Linux-only scientific application named "rcross," which added checkpointing and progress-bar support; this application was initially limited to Linux crunchers before being extended to other platforms.<ref name="bcteam" />

The project credited several volunteers by name for contributions beyond crunching, including a project logo designed by a volunteer known as "Cori," an image of Delaunay and Voronoi diagrams contributed by M. Sanner, a favicon by "Rebirther," translations into Russian, Polish and Italian by volunteer translators, and an official screensaver programmed by a volunteer known as "S@NL FilmFreak."<ref name="thankyou">{{Cite web |title=The Rectilinear Crossing Number Project: Thank You |url=http://dist.ist.tugraz.at/cape5/thankyou.html |publisher=Institute for Software Technology, Graz University of Technology |access-date=2026-07-01}}</ref>

=== Screensaver ===
The project's official BOINC screensaver, created by community volunteer "S@NL FilmFreak," visualized the crossing-minimization search in real time.<ref name="thankyou" /> A recorded playthrough of the screensaver has been preserved on video:

{{#ev:youtube|d03IUeQrDLQ|700|center|Rectilinear Crossing Number Project screensaver|start=0}}

== Results ==
The project's principal scientific result was the determination that the rectilinear crossing number of the complete graph on 18 vertices is
: <math>\overline{cr}(K_{18}) = 1029</math>,
a value the team described as having been found "after months of distributed computing."<ref name="oeis">{{Cite web |title=A014540: Rectilinear crossing number of complete graph on n nodes |url=https://oeis.org/A014540 |publisher=OEIS Foundation |access-date=2026-07-01}}</ref> This settled what had been, at the time, the smallest open case of the rectilinear crossing number problem.<ref name="why" />

The K18 value was subsequently confirmed and extended by other researchers, who additionally determined the values for <math>n = 20</math> and <math>n = 22</math> through <math>n = 27</math> using independent, non-distributed analytical methods; as of that work, the next unresolved case, <math>n = 28</math>, was narrowed to either 7233 or 7234.<ref name="oeis" /> An updated table of best known values for larger <math>n</math> continues to be maintained by Oswin Aichholzer.<ref>{{Cite web |title=On the Rectilinear Crossing Number |url=http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ |publisher=Oswin Aichholzer, Graz University of Technology |access-date=2026-07-01}}</ref>

The known values of <math>\overline{cr}(K_n)</math> for small <math>n</math>, including the K18 result attributed to the project, are catalogued in the [[wikipedia:On-Line Encyclopedia of Integer Sequences|On-Line Encyclopedia of Integer Sequences]] as sequence A014540.<ref name="oeis" />

== Publications ==

=== Papers that used data computed by the project ===

* {{Cite journal |last1=Ábrego |first1=B. M. |last2=Fernández-Merchant |first2=S. |last3=Leaños |first3=J. |last4=Salazar |first4=G. |title=The maximum number of halving lines and the rectilinear crossing number of Kn for n≤27 |journal=Electronic Notes in Discrete Mathematics |volume=30 |pages=261-266 |year=2008}} - [https://www.csun.edu/~ba70714/publications/Halving.pdf Confirmed the project's K18 result and extended exact values to K20 and K22 through K27.]

=== Related background and methodology papers ===
* {{Cite journal |last1=Aichholzer |first1=O. |last2=Aurenhammer |first2=F. |last3=Krasser |first3=H. |title=On the Crossing Number of Complete Graphs |journal=Computing |volume=76 |issue=1-2 |pages=165-176 |year=2006 |doi=10.1007/s00607-005-0133-3}} - [https://link.springer.com/article/10.1007/s00607-005-0133-3 Describes the abstract order type extension method underlying the project's search strategy], and establishes <math>\overline{cr}(K_{11}) = 102</math> and <math>\overline{cr}(K_{12}) = 153</math>.
* {{Cite journal |last1=Aichholzer |first1=O. |last2=Duque |first2=F. |last3=Fabila-Monroy |first3=R. |last4=García-Quintero |first4=O. E. |last5=Hidalgo-Toscano |first5=C. |title=An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants |journal=Journal of Graph Algorithms and Applications |volume=24 |issue=3 |pages=421-432 |year=2020 |arxiv=1907.07796}} - [https://arxiv.org/abs/1907.07796 Later continuation of research into asymptotic crossing constants building on the same problem area.]

== See also ==
* [[BOINC]]
* [[wikipedia:Crossing number (graph theory)|Crossing number (graph theory)]]
* [[wikipedia:Complete graph|Complete graph]]
* [[wikipedia:Computational geometry|Computational geometry]]

== External links ==
* {{URL|https://web.archive.org/web/20090101000000*/dist.ist.tugraz.at/cape5|Archived project website (Wayback Machine)}}
* {{URL|http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/|Oswin Aichholzer's rectilinear crossing number results page}}
* {{URL|https://oeis.org/A014540|OEIS sequence A014540}}

== References ==
{{Reflist}}

[[Category:Completed BOINC projects]]
[[Category:Mathematics projects]]

Rectilinear Crossing Number Project - Revision history

Al Piskun: first light