Blocking delaunay triangulations

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

*Korrespondierende/r Autor/-in für diese Arbeit

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

Abstract

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
Originalspracheenglisch
Seiten (von - bis)154-159
FachzeitschriftComputational Geometry
Jahrgang46
Ausgabenummer2
DOIs
PublikationsstatusVeröffentlicht - 2013

Fields of Expertise

  • Sonstiges

Treatment code (Nähere Zuordnung)

  • Theoretical

Fingerprint

Untersuchen Sie die Forschungsthemen von „Blocking delaunay triangulations“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren