Back to my homepage

5-Holes in point sets

We investiaged the minimum number of convex 5-holes in small point sets. The following table summarizes our knowledge on the values of $h_5(n)$ for $n \le 17$. Here $h_5(n)$ denotes the minimum number of 5-holes among all sets of $n$ points and $h_5^*(n)$ denotes the minimum number of 5-holes among all generalized point sets of size $n$. We omit the entry for $h_5^*(n)$ if it coincides with the one for $h_5(n)$.
$n$ $h_5(n)$ $h_5^*(n)$
9 0
10 1
11 2
12 3
13 3
14 6
15 9
16 11
17 ..16
18 ..21
19 ..26
20 ..33
21 ..39
22 ..46 ..45
23 ..53 ..52
24 ..62 ..60
25 ..72 ..69
26 ..80 ..77
27 ..90 ..87
28 ..103 ..99
29 ..119 ..115
30 ..137 ..129
31 ..154 ..147
32 ..175 ..167
33 ..195 ..190
34 ..226 ..216
35 ..251 ..237
36 ..268 ..261
37 ..291
38 ..309
39 ..351
40 ..373 ..348
50 ..731
60 ..1244
70 ..1875

Exact Values and Lower Bounds

Every set $P$ of $n$ points with $k=h_5(P)$ 5-holes implies that $h_5(n) \le k$, where $h_5(P)$ denotes the number of $5$-holes in $P.$ To show $h_5(n)=k$, it suffices to find a set of $n$ points with $k$ 5-holes and then show that there is no point set $P$ with $h_5(P) < k$. To determine the exact value of $h_5(n)$ for small values of $n$, we have two independent implementations. The basic idea behind both programs is to either find a set of $n$ points with at most $k$ 5-holes or show that no such point set exists. The first implementation, which was already described in the Bachelor's thesis of Scheucher, is based on the program for generating the database of order types. Points are iteratively added outside the convex hull of a generalized point set $P$ using abstract extension unless $|P|=n$ or $h_5(P) > k$. If $h_5(P) > k$, then any further point cannot decrease the number of 5-holes as we only add points outside of the convex hull. Our second implementation generates an integer linear program (ILP) instance to decide whether $h_5(P) \le k$, which then can be solved using GLPK package (GNU Linear Programming Kit). GLPK allows to transform the problem into a CNF-SAT instance, which can then be solved by Minisat (which is fully integrated in GLPK). We remark that one can also manually decode (bounded) integer variables by binary variables representing the binary-represention. The idea is to use binary variables Using these variables it is then possible to assign further binary variables to each tuple of five points (whether they form a 5-hole or not), and finally, to bound the sum over those binary variables, i.e., the number of 5-holes. We remark that such an ILPs makes use of signature functions and have $O(n^5)$ constraints in $O(n^4)$ variables.

The sourcecode of the second implementation can be downloaded here. It can be used to verify the values $h_5(9)=0$, $h_5(10)=1$, $h_5(11)=2$, $h_5(12)=3$, $h_5(13)=3$, $h_5(14)=6$, $h_5(15)=9$, and $h_5(16)=11$. The values of $h_5(9)$ and $h_5(10)$ were already determined by Harborth and the values of $h_5(11)$ and $h_5(12)$ were determined by Dehnhardt. The values of $h_5(13)$, $h_5(14)$, and $h_5(15)$ were determined in the Bachelor's thesis of Scheucher, where also $h_5(16) \in \{ 10,11\}$ was shown. The exact value $h_5(16)=11$ was determined recently using our second approach based on ILP. Concerning the running time of our computations (on a 2GHz CPU with GLPK LP/MIP Solver, v4.55), it took about

Concerning $h_5(17)\stackrel{?}{>}11$, the computation is running for 15 days now (Manfred, 10.03.2017).

Upper Bounds

Here we present sets of $n$ points for $n \le 40$ and $n=50,60,70$, with a small number of 5-holes (probably not minimum). Moreover, for $22 \le n \le 40$ we present some generalized point sets encoded by their small lambda matrices. For $n \le 25$, we can prove that the found generalized point sets are not realizable by point sets in the plane as they violate the Grassman-Pluecker relations. To be more precise, non-realizabilty of certain generalized point subsets was shown using GLPK with "exact arithmetics" (i.e., simplex method on rational numbers). However, even though these generalized point sets are not realizable, this does not imply that no (Euclidean) point set with that amount of 5-holes exists. For the generalized point sets we provide a visualization of their dual pseudoline arrangements.

The filename describes the number of points and the number of 5-holes. For example data/n0029c5h000115.psz shows a set of $n=29$ points with $h_5=115$ 5-holes.

Real


File: data/n0009c5h000000.psz


File: data/n0010c5h000001.psz


File: data/n0011c5h000002.psz


File: data/n0012c5h000003.psz


File: data/n0013c5h000003.psz


File: data/n0014c5h000006.psz


File: data/n0015c5h000009.psz


File: data/n0016c5h000011.psz


File: data/n0017c5h000016.psz


File: data/n0018c5h000021.psz


File: data/n0019c5h000026.psz


File: data/n0020c5h000033.psz


File: data/n0021c5h000039.psz


File: data/n0022c5h000046.psz


File: data/n0023c5h000053.psz


File: data/n0024c5h000062.psz


File: data/n0025c5h000072.psz


File: data/n0026c5h000080.psz


File: data/n0027c5h000090.psz


File: data/n0028c5h000103.psz


File: data/n0029c5h000119.psz


File: data/n0030c5h000137.psz


File: data/n0031c5h000154.psz


File: data/n0032c5h000175.psz


File: data/n0033c5h000195.psz


File: data/n0034c5h000226.psz


File: data/n0035c5h000251.psz


File: data/n0036c5h000268.psz


File: data/n0037c5h000291.psz


File: data/n0038c5h000309.psz


File: data/n0039c5h000351.psz


File: data/n0040c5h000373.psz


File: data/n0050c5h000731.psz


File: data/n0060c5h001244.psz


File: data/n0070c5h001875.psz

Abstract


File: data/n0022c5h000045.lt.nonr.lt


File: data/n0023c5h000052.lt.nonr.lt


File: data/n0024c5h000060.lt.nonr.lt


File: data/n0025c5h000069.lt.nonr.lt


File: data/n0026c5h000077.lt


File: data/n0027c5h000087.lt


File: data/n0028c5h000099.lt


File: data/n0029c5h000115.lt

File: data/n0030c5h000129.lt

File: data/n0031c5h000147.lt

File: data/n0032c5h000167.lt

File: data/n0033c5h000190.lt

File: data/n0034c5h000216.lt

File: data/n0035c5h000237.lt

File: data/n0036c5h000261.lt


File: data/n0040c5h000348.lt

Last update: 10.03.2017, (c) 2017 Manfred Scheucher