Blocking delaunay triangulations

Oswin Aichholzer, Ruy Fabila-Monroy, Thomas Hackl, Marc van Kreveld, Alexander Pilz, Pedro Ramos*, Birgit Vogtenhuber

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


Given a set B of n black points in general position, we say that a set of white points
W blocks B if in the Delaunay triangulation of B ∪ W there is no edge connecting two
black points. We give the following bounds for the size of the smallest set W blocking B:
(i) 3n/2 white points are always sufficient to block a set of n black points, (ii) if B is in
convex position, 5n/4 white points are always sufficient to block it, and (iii) at least n − 1
white points are always necessary to block a set of n black points
Original languageEnglish
Pages (from-to)154-159
JournalComputational Geometry
Issue number2
Publication statusPublished - 2013

Fields of Expertise

  • Sonstiges

Treatment code (Nähere Zuordnung)

  • Theoretical


Dive into the research topics of 'Blocking delaunay triangulations'. Together they form a unique fingerprint.

Cite this