title: Blocking Delaunay triangulations.
abstract: Given a setBofnblack points in general position, we say that a set of white pointsWblocksBif in the Delaunay triangulation of [Formula: see text] there is no edge connecting two black points. We give the following bounds for the size of the smallest setWblockingB: (i) [Formula: see text] white points are always sufficient to block a set ofnblack points, (ii) ifBis in convex position, [Formula: see text] white points are always sufficient to block it, and (iii) at least [Formula: see text] white points are always necessary to block a set ofnblack points.
authors.affiliation: Institute for Software Technology, University of Technology, Graz, Austria.
authors.forename: Oswin
authors.initials: O
authors.lastname: Aichholzer
authors.forename: Ruy
authors.initials: R
authors.lastname: Fabila-Monroy
authors.forename: Thomas
authors.initials: T
authors.lastname: Hackl
authors.forename: Marc
authors.initials: M
authors.lastname: van Kreveld
authors.forename: Alexander
authors.initials: A
authors.lastname: Pilz
authors.forename: Pedro
authors.initials: P
authors.lastname: Ramos
authors.forename: Birgit
authors.initials: B
authors.lastname: Vogtenhuber
keywords: Delaunay graph; Graph drawing; Proximity graphs; Witness graphs