**F. Aurenhammer, B. Su, Y.-F. Xu, and B. Zhu**

We consider a variant of visibility-constrained Voronoi diagrams for given
point sites in the Euclidean plane. Whereas such diagrams typically are of
size , the combinatorial and algorithmic complexity of the
studied variant is significantly subquadratic in .