Enumerating Order Types for Small Point Sets with Applications
This page contains information about the data base of order types for small point sets. Please refer to the related papers for more details on theory and applications and further background information. The provided files contain all inequivalent point sets (i.e. order types) as well as additional information computed from these sets.
For details on the file format, available files etc. we strongly recomment to consult the readme-file as well as the file on applications!
You can obtain realizations and information of point set order types from our database for sets of size 3 ... 10 by e-mail!
From this page you can download the database for up to 9 vertices. For n=10
the files have more than half a Gigabyte and are thus only available
on CD-Rom or via automatic e-mail queries.
Please e-mail us for information on how to get a copy of this CD.
Usage of the data base is free for non-commercial, non-governmental and
non-military purposes (please e-mail us otherwise). In any
case we would like you to inform us about your
investigations!
| Point sets, representing all order types | ||||
| Number of Points |
Number of sets |
File | 08 / 16 Bit | Filesize |
| 3 | 1 | otypes03.b08 | 08 | 6 |
| 4 | 2 | otypes04.b08 | 08 | 16 |
| 5 | 3 | otypes05.b08 | 08 | 30 |
| 6 | 16 | otypes06.b08 | 08 | 192 |
| 7 | 135 | otypes07.b08 | 08 | 1 890 |
| 8 | 3 315 | otypes08.b08 | 08 | 53 040 |
| 9 | 158 817 | otypes09.b16 | 16 | 5 717 412 |
| 10 | 14 309 547 | only on CD | 16 | 572 381 880 |
| 11 | 2 334 512 907 | only on CD | 16 | -- |
| Crossing number | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | crossn03.b08 | 08 | 1 |
| 4 | crossn04.b08 | 08 | 2 |
| 5 | crossn05.b08 | 08 | 3 |
| 6 | crossn06.b08 | 08 | 16 |
| 7 | crossn07.b08 | 08 | 135 |
| 8 | crossn08.b08 | 08 | 3 315 |
| 9 | crossn09.b08 | 08 | 158 817 |
For more on crossing numbers, especially results for n=11 and n=12 see my page on Rectilinear Crossing Numbers.
| Number of Crossing Families | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | crossf03.b08 | 08 | 1 |
| 4 | crossf04.b08 | 08 | 2 |
| 5 | crossf05.b08 | 08 | 3 |
| 6 | crossf06.b08 | 08 | 16 |
| 7 | crossf07.b08 | 08 | 135 |
| 8 | crossf08.b08 | 08 | 3 315 |
| 9 | crossf09.b08 | 08 | 158 817 |
| Number of Extreme Points | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | extrem03.b08 | 08 | 1 |
| 4 | extrem04.b08 | 08 | 2 |
| 5 | extrem05.b08 | 08 | 3 |
| 6 | extrem06.b08 | 08 | 16 |
| 7 | extrem07.b08 | 08 | 135 |
| 8 | extrem08.b08 | 08 | 3 315 |
| 9 | extrem09.b08 | 08 | 158 817 |
| Number of k-gons | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | kgons03.b08 | 08 | 1 |
| 4 | kgons04.b08 | 08 | 4 |
| 5 | kgons05.b08 | 08 | 9 |
| 6 | kgons06.b08 | 08 | 64 |
| 7 | kgons07.b08 | 08 | 675 |
| 8 | kgons08.b08 | 08 | 19 890 |
| 9 | kgons09.b08 | 08 | 1 111 719 |
| Number of Empty k-gons | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | ekgons03.b08 | 08 | 1 |
| 4 | ekgons04.b08 | 08 | 4 |
| 5 | ekgons05.b08 | 08 | 9 |
| 6 | ekgons06.b08 | 08 | 64 |
| 7 | ekgons07.b08 | 08 | 675 |
| 8 | ekgons08.b08 | 08 | 19 890 |
| 9 | ekgons09.b08 | 08 | 1 111 719 |
| Convex Cover Number | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | ccover03.b08 | 08 | 1 |
| 4 | ccover04.b08 | 08 | 2 |
| 5 | ccover05.b08 | 08 | 3 |
| 6 | ccover06.b08 | 08 | 16 |
| 7 | ccover07.b08 | 08 | 135 |
| 8 | ccover08.b08 | 08 | 3 315 |
| 9 | ccover09.b08 | 08 | 158 817 |
| Convex Partition Number | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | cpart03.b08 | 08 | 1 |
| 4 | cpart04.b08 | 08 | 2 |
| 5 | cpart05.b08 | 08 | 3 |
| 6 | cpart06.b08 | 08 | 16 |
| 7 | cpart07.b08 | 08 | 135 |
| 8 | cpart08.b08 | 08 | 3 315 |
| 9 | cpart09.b08 | 08 | 158 817 |
| Convex Decomposition Number | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | decomp03.b08 | 08 | 1 |
| 4 | decomp04.b08 | 08 | 2 |
| 5 | decomp05.b08 | 08 | 3 |
| 6 | decomp06.b08 | 08 | 16 |
| 7 | decomp07.b08 | 08 | 135 |
| 8 | decomp08.b08 | 08 | 3 315 |
| 9 | decomp09.b08 | 08 | 158 817 |
| Number of Triangulations | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | trinum03.b08 | 08 | 1 |
| 4 | trinum04.b08 | 08 | 2 |
| 5 | trinum05.b08 | 08 | 3 |
| 6 | trinum06.b08 | 08 | 16 |
| 7 | trinum07.b08 | 08 | 135 |
| 8 | trinum08.b08 | 08 | 3 315 |
| 9 | trinum09.b16 | 16 | 317 634 |
| Number of Minimum Pseudo-Triangulations | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| Data provided by Lutz Kettner and Herve Brönniman, see the PT Homepage | |||
| 3 | pseudo03.b08 | 08 | 1 |
| 4 | pseudo04.b08 | 08 | 2 |
| 5 | pseudo05.b08 | 08 | 3 |
| 6 | pseudo06.b08 | 08 | 16 |
| 7 | pseudo07.b16 | 16 | 270 |
| 8 | pseudo08.b16 | 16 | 6 630 |
| 9 | pseudo09.b16 | 16 | 317 634 |
| Number of Rectilinear Crossing-Free Hamiltonian Cycles | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | hamilt03.b08 | 08 | 1 |
| 4 | hamilt04.b08 | 08 | 2 |
| 5 | hamilt05.b08 | 08 | 3 |
| 6 | hamilt06.b08 | 08 | 16 |
| 7 | hamilt07.b08 | 08 | 135 |
| 8 | hamilt08.b16 | 16 | 6 630 |
| 9 | hamilt09.b16 | 16 | 317 634 |
| Minimum Number of Reflex Angles in Simple Polygonalizations | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | reflex03.b08 | 08 | 1 |
| 4 | reflex04.b08 | 08 | 2 |
| 5 | reflex05.b08 | 08 | 3 |
| 6 | reflex06.b08 | 08 | 16 |
| 7 | reflex07.b08 | 08 | 135 |
| 8 | reflex08.b08 | 08 | 3 315 |
| 9 | reflex09.b08 | 08 | 158 817 |
| Number of Crossing-Free Spanning Trees | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | cfspan03.b08 | 08 | 1 |
| 4 | cfspan04.b08 | 08 | 2 |
| 5 | cfspan05.b08 | 08 | 3 |
| 6 | cfspan06.b16 | 16 | 32 |
| 7 | cfspan07.b16 | 16 | 270 |
| 8 | cfspan08.b32 | 32 | 13 260 |
| 9 | cfspan09.b32 | 32 | 635 268 |
| Number of Crossing-Free Matchings | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | match03.b08 | 08 | 1 |
| 4 | match04.b08 | 08 | 2 |
| 5 | match05.b08 | 08 | 3 |
| 6 | match06.b08 | 08 | 16 |
| 7 | match07.b08 | 08 | 135 |
| 8 | match08.b08 | 08 | 3 315 |
| 9 | match09.b16 | 16 | 317 634 |
| Number of k-sets | |||
| Number of Points |
File | 08 / 16 Bit | Filesize |
| 3 | kset03.b08 | 08 | 1 |
| 4 | kset04.b08 | 08 | 4 |
| 5 | kset05.b08 | 08 | 6 |
| 6 | kset06.b08 | 08 | 48 |
| 7 | kset07.b08 | 08 | 405 |
| 8 | kset08.b08 | 08 | 13 260 |
| 9 | kset09.b08 | 08 | 635 268 |