Here we store the experimental results described in

- O. Aichholzer, M. Balko, T. Hackl, J. Kynčl, I. Parada, M. Scheucher, P. Valtr, and B. Vogtenhuber.
*A superlinear lower bound on the number of 5-holes*, in preparation (2016).

**Abstract:**
Let *P* be a finite set of points in the plane in *general position*, that is, no three points of *P* are on a common line.
We say that a set *H* of five points from *P* is a *5-hole in P* if *H* is the vertex set of a convex 5-gon containing no other points of *P*.
For a positive integer *n*, let *h*_{5}(n) be the minimum number of 5-holes among all sets of *n* points in the plane in general position.

Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for *h*_{5}(n) have been of order *Ω(n)* and *O(n*^{2}), respectively.
We show that *h*_{5}(n) = Ω(n log^{4/5}(n)), obtaining the first superlinear lower bound on *h*_{5}(n).

The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound.
If a finite set *P* of points in the plane in general position is partitioned by a line *l* into two subsets, each of size at least 5 and not in convex position, then *l* intersects the convex hull of some 5-hole in *P*.
The proof of this result is computer-assisted.

Further details can be found in the paper.

**Results:**
Here we store four programs that are used to verify the following four statements from the proof of the lower bound on the number of 5-holes in a point set *P*.
The definitions that are used in the statements can be found in the paper. We note that Manfred Scheucher wrote an independent implementation of the proofs of these statements.

**Computer lemma 1**

Let *P = A ∪ B* be an *l*-divided set with *|A| = 5*, *|B| = 6*, and with *A* not in convex position.
Then there is an *l*-divided 5-hole in *P*.

**Computer lemma 2**

Let *P = A ∪ B* be an *l*-divided set with no *l*-divided 5-hole in *P*, *|A| = 5*, *4 ≤ |B| ≤ 6*, and with *A* in convex position.
Then, for every point *a* of *A*, every convex *a*-wedge contains at most two points of *B*.

**Computer lemma 3**

Let *P = A ∪ B* be an *l*-divided set with no *l*-divided 5-hole in *P*, *|A| = 6*, and *|B| = 5*.
Then, for every point *a* of *A*, every convex *a*-wedge contains at most two points of *B*.

**Computer lemma 4**

Let *P = A ∪ B* be an *l*-divided set with no *l*-divided 5-hole in *P*, *5 ≤ |A| ≤ 6*, *|B| = 4*, and with *A* in convex position.
Then, for every point *a* of *A*, if the non-convex *a*-wedge is empty of points of *B*, every *a*-wedge contains at most two points of *B*.

**Programs:**
All programs were implemented in C++ and they use the same approach that is based on so-called signature functions, which are an abstraction of finite point sets in the plane in general position.
Every (generalized) configuration *P* of *n* points, which are ordered according to their increasing x-coordinates, can be described by specifying the orientation of each of its triangles.
The * signature function* of a *P* is the vector of these orientations, which are called *signs*.
It is known that signature functions are characterized by a list of eight forbidden 4-tuples of signs that are induced by 4-tuples of points.

Every generalized configuration *P* of *n* points is stored as a {0,1}-vector whose length is the number of triples of points of *P*.
The coordinates of this vector are triples (*a*,*b*,*c*), 1 <= *a* < *b* < *c* <= *n*, in the lexicographic order where a triple is assigned 1 if the corresponding triangle in *P* is oriented counterclockwise and 0 otherwise.

Let *A* and *B* be two point sets whose signature functions are given on the input.
Each program fills the signs of *A* and *B* into the signature function of an *n = |A| + |B|* point set so that *A* is induced on the first *|A|* points and *B* is induced on the last *|B|* points of the constructed set.
Then the program tries to assign all the remaining signs to obtain an *l*-divided set *P = A ∪ B*.
This is done by performing a simple depth-first search algorithm.
We cut each branch of this search whenever we assign a sign that produces a non-valid 4-tuple of signs or whenever we obtain an *l*-divided 5-hole in the constructed point set.
After assigning a new sign, we also check whether the forbidden 4-tuples of signs force new signs to be assigned.
Once all signs are assigned, we check the corresponding condition on the obtained (generalized) point set *P*.

The search is done for every pair *(A,B)* of point sets that satisfy the assumptions of the corresponding lemma.
The list of all such pairs *(A,B)* is given on the input and it was obtained using a similar exhaustive search through signature functions.
The sets *A* are stored in a single file as a list of their signature functions and similarly for the sets *B*.
For points sets of size eleven, the running time of the programs can be about hundreds of hours.
However, every program allows parallel executions by specifying which pairs *(A,B)* should be checked.

Each program stops either when it finds a (generalized) point set *P* that does not satisfy the condition from the corresponding lemma, or if it checks all the pairs *(A,B)* without finding any such set.
If the latter case occurs, then the corresponding lemma is verified.

**Program and input files for Computer lemma 1** [ZIP]

To use the program under a Linux system do the following.

- Save the program 'computerLemma1.cpp' and its input files 'A5Nonconvex.txt' and 'B6.txt' to a single directory on your computer.
- For parallel executions, change the following parameters:
*start* = the number of the first point set *A* to be checked,
*end* = the number of the last point set *A* to be checked.
- The parameters
*start* and *end* must be in the following range: 0 ≤ *start* < *end* ≤ 908.

- Compile the program with the command 'g++ computerLemma1.cpp -o computerLemma1'.
- Run the program with the command './computerLemma1'.

**Program and input files for Computer lemma 2** [ZIP]

To use the program under a Linux system do the following.

- Save the program 'computerLemma2.cpp' and its input files 'A5Convex.txt', 'B4.txt', 'B5.txt', and 'B6.txt' to a single directory on your computer.
- To specify the set
*B*, change the following parameters:
*MB* = the size of the point set *B*,
*numberOfConfB* = number of the sets *B* on the input,
*filenameB* = the name of the input file for *B*.
- The parameters (
*MB*, *numberOfConfB*, *filenameB*) should attain the following values: (*4*, *8*, *"B4.txt"*), (*5*, *62*, *"B5.txt"*), (*6*, *908*, *"B6.txt"*)

- For parallel executions, change the following parameters:
*start* = the number of the first point set *A* to be checked,
*end* = the number of the last point set *A* to be checked.
- The parameters
*start* and *end* must be in the following range: 0 ≤ *start* < *end* ≤ 8.

- Compile the program with the command 'g++ computerLemma2.cpp -o computerLemma2'.
- Run the program with the command './computerLemma2'.

**Program and input files for Computer lemma 3** [ZIP]

To use the program under a Linux system do the following.

- Save the program 'computerLemma3.cpp' and its input files 'A6.txt' and 'B5Convex.txt' to a single directory on your computer.
- For parallel executions, change the following parameters:
*start* = the number of the first point set *A* to be checked,
*end* = the number of the last point set *A* to be checked.
- The parameters
*start* and *end* must be in the following range: 0 ≤ *start* < *end* ≤ 908.

- Compile the program with the command 'g++ computerLemma3.cpp -o computerLemma3'.
- Run the program with the command './computerLemma3'.
- We note that, by Computer lemma 1, it is sufficient to verify the statement for B in convex position.

**Program and input files for Computer lemma 4** [ZIP]

To use the program under a Linux system do the following.

- Save the program 'computerLemma4.cpp' and its input files 'A5Convex.txt', 'A6Convex.txt', and 'B4.txt' to a single directory on your computer.
- To specify the set
*A*, change the following parameters:
*MA* = the size of the point set *A*,
*numberOfConfA* = number of the sets *A* on the input,
*filenameA* = the name of the input file for *A*.
- The parameters (
*MA*, *numberOfConfA*, *filenameA*) should attain the following values: (*5*, *8*, *"A5Convex.txt"*), (*6*, *16*, *"A6Convex.txt"*)

- For parallel executions, change the following parameters:
*start* = the number of the first point set *A* to be checked,
*end* = the number of the last point set *A* to be checked.
- The parameters
*start* and *end* must be in the following range: 0 ≤ *start* < *end* ≤ *numberOfConfA*.

- Compile the program with the command 'g++ computerLemma4.cpp -o computerLemma4'.
- Run the program with the command './computerLemma4'.

A compressed directory with all the programs and input files: [ZIP, 28 kB]

Last update: 5.12.2016