We consider the problem of projecting a point in a polyhedral set onto the
boundary of the set using an arbitrary norm for the projection. Two types o
f polyhedral sets, one defined by a convex combination of k points in R-n a
nd the second by the intersection of m closed half-spaces in R-n, lead to d
isparate optimization problems for finding such a projection. The first cas
e leads to a mathematical program with a linear objective function and cons
traints that are linear inequalities except for a single nonconvex cylindri
cal constraint. Interestingly, for the 1-norm, this nonconvex problem can b
e solved by solving 2n linear programs. The second polyhedral set leads to
a much simpler problem of determining the minimum of m easily evaluated num
bers. These disparate mathematical complexities parallel known ones for the
related problem of finding the largest ball, with radius measured by an ar
bitrary norm, that can be inscribed in the polyhedral set. For a polyhedral
set of the first type this problem is NP-hard for the 2-norm and the infin
ity-norm [R. M. Freund and J. B. Orlin, Math. Programming, 33 (1985), pp. 1
39-145] and solvable by a single linear program for the 1-norm [P. Gritzman
n and V. Klee, Math. Programming, 59 (1993), pp. 163-213], while for the se
cond type this problem leads to a single linear program even for a general
norm [P. Gritzmann and V. Klee, Discrete Comput. Geom., 7 (1992), pp. 255-2
80].