论文标题
阻止外部的Delaunay三角剖分
Blocking Delaunay Triangulations from the Exterior
论文作者
论文摘要
给定两个不同的点集$ p $和$ q $在飞机上，我们说$ q $ \ emph {blocks} $ p $如果在任何$ p \ cup Q $的delaunay三角测量中都没有$ p $的两个点。 Aichholzer等。 （2013年）表明，任何$ n $ n $的$ p $一般位置都可以被$ \ frac {3} {2} n $点阻止，并且每个集合位置的$ n $ point的$ n $ point都可以被$ \ frac {5} {4} {4} n $点阻止。此外，他们推测，如果$ p $处于凸位，则$ n $ blove点足够且必要。 Biniaz（2021）最近表明了这一必要性，他证明了以$ n $ n $阻止点设定的每个点。 在这里，我们研究了变体，其中阻止点只能位于给定点集的凸壳之外。我们表明$ \ frac {5} {4} n-o（1）$ sise \ emph {外部阻止}点有时是必要的，即使给定点集在凸位位置。因此，如果Aichholzer等人的猜想，我们得到了这一点。对于原始设置是正确的，那么某些点配置的最小阻塞集$ p $必须包含$ p $的凸船体内部的点。
Given two distinct point sets $P$ and $Q$ in the plane, we say that $Q$ \emph{blocks} $P$ if no two points of $P$ are adjacent in any Delaunay triangulation of $P\cup Q$. Aichholzer et al. (2013) showed that any set $P$ of $n$ points in general position can be blocked by $\frac{3}{2}n$ points and that every set $P$ of $n$ points in convex position can be blocked by $\frac{5}{4}n$ points. Moreover, they conjectured that, if $P$ is in convex position, $n$ blocking points are sufficient and necessary. The necessity was recently shown by Biniaz (2021) who proved that every point set in general position requires $n$ blocking points. Here we investigate the variant, where blocking points can only lie outside of the convex hull of the given point set. We show that $\frac{5}{4}n-O(1)$ such \emph{exterior-blocking} points are sometimes necessary, even if the given point set is in convex position. As a consequence we obtain that, if the conjecture of Aichholzer et al. for the original setting was true, then minimal blocking sets of some point configurations $P$ would have to contain points inside of the convex hull of $P$.
