  In the Hausdorff Voronoi diagram of a family of \emph{clusters of points} in
the plane, the distance between a point $t$ and a cluster $P$ is measured as
the maximum distance between $t$ and any point in $P$, and the diagram is
defined in a nearest-neighbor sense for the input clusters. In this paper we
consider %El."non-crossing" \emph{non-crossing} clusters in the plane, for
which the combinatorial complexity of the Hausdorff Voronoi diagram is linear
in the total number of points, $n$, on the convex hulls of all clusters. We
present a randomized incremental construction, based on point location, that
computes this diagram in expected $O(n\log^2{n})$ time and expected $O(n)$
space. Our techniques efficiently handle non-standard characteristics of
generalized Voronoi diagrams, such as sites of non-constant complexity, sites
that are not enclosed in their Voronoi regions, and empty Voronoi regions. The
diagram finds direct applications in VLSI computer-aided design.
