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 (the Delaunay triangulation of) any set P of n points in general position (that is, no three collinear and no four cocircular) 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 .
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 .
| Originalsprache | englisch |
|---|---|
| Titel | Proc. 38th European Workshop on Computational Geometry (EuroCG 2022) |
| Erscheinungsort | Perugia, Italy |
| Seiten | 9:1-9:7 |
| Publikationsstatus | Veröffentlicht - 2022 |
| Veranstaltung | 38th European Workshop on Computational Geometry: EuroCG 2022 - Engineering Department of the University of Perugia, Perugia, Italien Dauer: 14 März 2022 → 16 März 2022 https://eurocg2022.unipg.it/ |
Konferenz
| Konferenz | 38th European Workshop on Computational Geometry |
|---|---|
| Kurztitel | EuroCG 2022 |
| Land/Gebiet | Italien |
| Ort | Perugia |
| Zeitraum | 14/03/22 → 16/03/22 |
| Internetadresse |
Fields of Expertise
- Information, Communication & Computing