On disjoint holes in point sets

Main Article Content

Manfred Scheucher


Given a set of points $S \subseteq \mathbb{R}^2$, a subset $X \subseteq S$, $|X|=k$, is called \emph{$k$-gon} if all points of $X$ lie on the boundary of $\mathrm{conv} (X)$, and \emph{$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 \emph{disjoint} 5-holes, that is, holes with disjoint respective convex hulls. This answers a question of Hosono and Urabe (2001).
In a recent article, Hosono and Urabe (2018) present new results on interior-disjoint holes -- a variant, which also has been investigated in the last two decades. Using our program, we show that every set of 15 points contains two interior-disjoint 5-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).

Article Details

How to Cite
Scheucher, M. (2019). On disjoint holes in point sets. Acta Mathematica Universitatis Comenianae, 88(3), 1049-1056. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1180/761