  We present a generalization of a combinatorial result by Aggarwal, Guibas,
Saxe and Shor [Discrete & Computational Geometry, 1989] on a linear-time
algorithm that selects a constant fraction of leaves, with pairwise disjoint
neighborhoods, from a binary tree embedded in the plane. This result of
Aggarwal et al. is essential to the linear-time framework, which they also
introduced, that computes certain Voronoi diagrams of points with a tree
structure in linear time. An example is the diagram computed while updating the
Voronoi diagram of points after deletion of one site. Our generalization allows
that only a fraction of the tree leaves is considered, and it is motivated by
linear-time Voronoi constructions for non-point sites. We are given a plane
tree $T$ of $n$ leaves, $m$ of which have been marked, and each marked leaf is
associated with a neighborhood (a subtree of $T$) such that any two
topologically consecutive marked leaves have disjoint neighborhoods. We show
how to select in linear time a constant fraction of the marked leaves having
pairwise disjoint neighborhoods.
