Back to my homepage
# On Disjoint Holes in Point Sets

This website provides programs to verify
the computer-assisted results from my paper
"On Disjoint Holes in Point Sets".
## Abstract of the paper

Given a set of points $S \subseteq \mathbb{R}^2$,
a subset $X \subseteq S$, $|X|=k$, is called
*$k$-gon* if all points of $X$ lie on the boundary of the convex hull $\mathrm{conv} (X)$,
and *$k$-hole* if, in addition, no point of $S \setminus X$ lies in $\mathrm{conv} (X)$.
We use computer assistance to show that every set of 17 points in general position
admits two disjoint 5-holes, that is, holes with disjoint respective convex hulls.
This answers a question of Hosono and Urabe (2001).
We also provide new bounds for three and more pairwise disjoint holes.
Moreover, our program can be used to verify
that every set of 17 points contains a 6-gon
within significantly smaller computation time
than the original program by Szekeres and Peters (2006).
## Short description of the programs

We provide a python program "h55.py" to formulate a SAT instance
to verify that every set of 17 points contains two disjoint 5-holes.
To execute the program, run

(The programs for interior-disjoint 5-holes and 6-gons are analogously.)## Downloads

python h55.py 17The SAT instance is written to a cnf-file, which then can be solved using a SAT solver such as glucose or picosat.

(The programs for interior-disjoint 5-holes and 6-gons are analogously.)

- The source code of the program "h55.py" to verify that every set of 17 points contains two disjoint 5-holes, i.e., $h(5,5)=17$. [download]
- The source code of the program "h55_interior.py" to verify that every set of 15 points contains two interior-disjoint 5-holes. [download]
- The source code of the program "g6.py" to verify that every set of 17 points contains a 6-gon, i.e., $g(6)=17$. [download]