Projects per year
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
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 language  English 

Pages (fromto)  154159 
Journal  Computational Geometry 
Volume  46 
Issue number  2 
DOIs  
Publication status  Published  2013 
Fields of Expertise
 Sonstiges
Treatment code (Nähere Zuordnung)
 Theoretical
Fingerprint
Dive into the research topics of 'Blocking delaunay triangulations'. Together they form a unique fingerprint.Projects
 3 Finished

FWF  ComPoSe  EuroGIAG_ErdösSzekeres type problems for colored point sets and compatible graphs
1/10/11 → 31/12/15
Project: Research project

FWF  CPGG  Combinatorial Problems on Geometric Graphs
Hackl, T.
1/09/11 → 31/12/15
Project: Research project

FWF  Computational geometry  NFN Industrial Geometry
Vogtenhuber, B., Aigner, W., Hackl, T., Grohs, P., Karpenkov, O., Kornberger, B., Wallner, J., Aichholzer, O. & Müller, C.
1/04/05 → 31/12/11
Project: Research project