  We give the first exact algorithmic study of facility location problems that
deal with finding a median for a continuum of demand points. In particular, we
consider versions of the ``continuous k-median (Fermat-Weber) problem'' where
the goal is to select one or more center points that minimize the average
distance to a set of points in a demand region. In such problems, the average
is computed as an integral over the relevant region, versus the usual discrete
sum of distances. The resulting facility location problems are inherently
geometric, requiring analysis techniques of computational geometry. We provide
polynomial-time algorithms for various versions of the L1 1-median
(Fermat-Weber) problem. We also consider the multiple-center version of the L1
k-median problem, which we prove is NP-hard for large k.
