A superlinear lower bound on the number of 5-holes

Homepage

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 h5(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 h5(n) have been of order Ω(n) and O(n2), respectively. We show that h5(n) = Ω(n log4/5(n)), obtaining the first superlinear lower bound on h5(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
Valid XHTML 1.0 Transitional