Abstract
Given two distinct point sets P and Q in the plane, we say that Q blocks P if no two
points of P are adjacent in any Delaunay triangulation of P ∪ Q. Aichholzer et al. (2013)
showed that any set P of n points in general position can be blocked by 3/2 n points and that every set P of n points in convex position can be blocked by 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 5/4 n − O(1) such 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 .
points of P are adjacent in any Delaunay triangulation of P ∪ Q. Aichholzer et al. (2013)
showed that any set P of n points in general position can be blocked by 3/2 n points and that every set P of n points in convex position can be blocked by 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 5/4 n − O(1) such 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 .
Original language | English |
---|---|
Publisher | arXiv |
Number of pages | 10 |
Publication status | Published - 21 Oct 2022 |
Keywords
- cs.CG
- cs.DM